分类存档：默认分类

【题目大意】给定一个有向图和源汇，求图中割点的个数

【算法分析】这题比较神，做法是将每个点拆点，然后中间连边流量为1，图中的边连边流量为inf，然后比较特殊的是S和T所拆得点间流量为2。然后这样的话，如果流量为2，那么图中除了S和T没有割点。如果流量为1，那么增广路上的有可能是割点，然后利用求最小割的dfs算法求出各个割。如果流量为0的话，那么说明S和T本来就不连通，所以任何一个点都是割点。

【其它】1WA，因为flow=2时特判错了，写成了0.低级错误啊…

2078969 2010-02-09 15:56:54 Accepted 3313 3156MS 12964K 2496 B G++ cwj

【CODE】

#include #include const int N=222222;
const int inf=(0x7FFFFFFF–10)/2;
struct gtp{int x,y,c,op,next;}g[1000000];
int n,m,e,S,T,ls[N],fa[N],v[N],list[N],ans,zgl[N],tt;

void addedge(int x,int y,int c){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e–1;
    g[e].next=ls[y]; ls[y]=e;
}   

void init(){
    e=0;
    memset(ls,0,sizeof(ls));
    memset(zgl,0,sizeof(zgl));
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x+n,y,inf);
    }
    scanf("%d%d",&S,&T);
    for (int i=0;i<n;i++)
      if (i!=S && i!=T) addedge(i,i+n,1);
                   else addedge(i,i+n,2);
    T+=n;
}

bool bfs(){
    for (int i=0;i<2*n;i++) v[i]=0;
    int head=0,tail=1;
    list[1]=S;
    while (head!=tail){
        head++;
        for (int t=ls[list[head]];t;t=g[t].next)
          if (!v[g[t].y] && g[t].c){
              v[g[t].y]=1;
              tail++;
              list[tail]=g[t].y;
              fa[g[t].y]=t;
          }
    }
    if (v[T]) return true;
    return false;
}   

void change(){
    for (int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c–;
        g[g[fa[i]].op].c++;
        zgl[i]=1;
    }   
    zgl[S]=1;
}   

int ek(){
    bool flag=bfs();
    if (!bfs()) return 0;
    change();
    flag=bfs();
    if (!bfs()) return 1;
    return 2;
}   

void dfs(int k){
    tt++;
    list[tt]=k;
    v[k]=1;
    for (int t=ls[k];t;t=g[t].next)
      if (g[t].c && !v[g[t].y]) dfs(g[t].y);
}   

void work(){
    g[ls[S]].c=0;
    g[ls[T–n]].c=0;
    memset(v,0,sizeof(v));
    ans=0;
    int st=S;
    for (;;){
        tt=0;
        dfs(st);
        bool flag=false;
        for (int i=1;i<=tt;i++) if (!flag)
          for (int t=ls[list[i]];t;t=g[t].next)
            if ((t&1) && !g[t].c && !v[g[t].y]){
                ans++;
                flag=true;
                st=g[t].y;
                if (g[t].y==T) return;
            }   
    }   
}   

int main(){
    while (scanf("%d%d",&n,&m)!=EOF){
        init();
        if (S+n==T){
            printf("1n");
            continue;
        }   
        int flow=ek();
        if (flow==0) printf("%dn",n);
        else
        if (flow==2) printf("2n");
        else{
            work();
            printf("%dn",ans);
        }   
    }   
}   

【题目大意】

给定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);
    }   
}