[HDU 3311]状态压缩、spfa扩展、有多余点的最小生成树**

【题目大意】

给定N个寺庙,和M个另外的地方。

然后给定点权,表示在这个点挖水井需要的代价。

再给定边权,为建造无向边i,j的代价。

然后求怎样弄最小的代价使得前N个点,就是寺庙都能得到水。

【算法分析】

我是这样想的,实际上如果把所有的水井都当成一个点S,点权转化为S与该点连边的权值。这样就相当于求用最小的代价,使得S和前N个点成为同一连通分量。

由于可以有多余的点,所以不能MST。

我们可以设D[I,J]表示目前到达第i个点,然后前N个点,包括新增点S的遍历情况为j(j用二进制表示)

然后用spfa扩展,最后求最小的d[i][(1<<(n+1))-1]就行了

【其它】WA几次,然后找来xt大牛的程序对拍。。。发现随机小数据随了几百个(用bat)全部答案一样,于是就囧了。。。

最后发现居然是:spfa的队列大小没有*64

由于XT大牛在比赛之后没有交,于是偶很可耻地成了本题放出来以后第一个AC的烧饼

Rank Author Exe. Time Exe. Memory Code Len. Language Date 1 cwj 1343MS 1136K 1895B G++ 2010-02-07 17:32:39

【CODE】

#include #include const int E=40000;
const
int N=2000;
const
int N2=N*64;
struct
gtp{int y,w,next;}g[E];
int
n,m,p,e;
int
ls[N],d[N][64],point[N2],state[N2];
bool
v[N][64];

void addedge(int x,int y,int w){
    e++;
    g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}
   

void init(){
    e=0; memset(ls,0,sizeof(ls));
    for
(int i=1;i<=n+m;i++){
        int
x;
        scanf("%d",&x);
        addedge(0,i,x);
        addedge(i,0,x);
    }

    for
(int i=1;i<=p;i++){
        int
x,y,w;
        scanf("%d %d %d",&x,&y,&w);
        addedge(x,y,w);
        addedge(y,x,w);
    }   
}
   

void spfa(){
    memset(d,50,sizeof(d));
    memset(v,false,sizeof(v));
    int
head=0,tail=0;
    for
(int i=0;i<=n+m;i++) d[i][0]=0;
    for
(int i=0;i<=n;i++){
        d[i][1<<i]=0;
        tail++;
        point[tail]=i;
        state[tail]=1<<i;
        v[i][1<<i]=true;
    }

    while
(head!=tail){
        head++; if (head>=N2) head=0;
        for
(int t=ls[point[head]];t;t=g[t].next)
          for
(int ts=0;ts<(1<<(n+1));ts++)
            if
(d[point[head]][state[head]]+g[t].w+d[g[t].y][ts]<d[g[t].y][ts|state[head]]){
                d[g[t].y][ts|state[head]]=d[point[head]][state[head]]+g[t].w+d[g[t].y][ts];
                if
(!v[g[t].y][ts|state[head]]){
                    v[g[t].y][ts|state[head]]=true;
                    tail++; if (tail>=N2) tail=0;
                    point[tail]=g[t].y;
                    state[tail]=(ts|state[head]);
                }   
            }

        v[point[head]][state[head]]=false;
    }   
}
   

int main(){
    while
(scanf("%d %d %d",&n,&m,&p)!=EOF){
        init();
        spfa();
        int
ans=0x7FFFFFFF;
        for
(int i=0;i<=n+m;i++)
          if
(d[i][(1<<(n+1))-1]<ans) ans=d[i][(1<<(n+1))-1];
        printf("%dn",ans);
    }   
}
   

留下评论

您的电子邮箱地址不会被公开。