POJ 1966 求无向图点连通度

叁歲伎倆 2021-12-22 14:15 256阅读 0赞

思路：  
n^2枚举（必须要n^2枚举啊）+拆点

特此嘲讽网上诸多垃圾题解，你们许多都是错的 —yyh

//By SiriusRen
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define N 5555
    int n,m,xx,yy,inf=0x3fffff,ans,ed=105;
    struct Node{
         int x,y;}point[N];
    struct Dinic{
        int first[107],next[N],v[N],w[N],tot,vis[107];
        void solve(int x,int y){
            memset(first,-1,sizeof(first)),tot=0;
            add(0,x,inf),add(x,x+n,inf),add(y,y+n,inf),add(y+n,105,inf);
            for(int i=1;i<=n;i++)add(i,i+n,1);
            for(int i=1;i<=m;i++)add(point[i].x+n,point[i].y,inf),add(point[i].y+n,point[i].x,inf);
            ans=min(ans,x=flow());
        }
        void add(int x,int y,int z){Add(x,y,z),Add(y,x,0);}
        void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}
        bool tell(){
            memset(vis,-1,sizeof(vis)),vis[0]=0;
            queue<int>q;q.push(0);
            while(!q.empty()){
                int t=q.front();q.pop();
                for(int i=first[t];~i;i=next[i])
                    if(vis[v[i]]==-1&&w[i])
                        vis[v[i]]=vis[t]+1,q.push(v[i]);
            }
            return vis[ed]!=-1;
        }
        int zeng(int x,int y){
            if(x==ed)return y;
            int r=0;
            for(int i=first[x];~i&&y>r;i=next[i])
                if(vis[v[i]]==vis[x]+1&&w[i]){
                    int t=zeng(v[i],min(y-r,w[i]));
                    w[i]-=t,w[i^1]+=t,r+=t;
                }
            if(!r)vis[x]=-1;
            return r;
        }
        int flow(){
            int jy=0,tmp;
            while(tell())while(tmp=zeng(0,inf))jy+=tmp;
            return jy;
        }
    }dinic;
    int main(){
        while(~scanf("%d%d",&n,&m)){
            ans=inf;
            for(int i=1;i<=m;i++){
                scanf(" (%d,%d)",&point[i].x,&point[i].y);
                point[i].x++,point[i].y++;
            }
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(i!=j)dinic.solve(i,j);
            if(ans==inf)printf("%d\n",n);
            else printf("%d\n",ans);
        }
    }

![这里写图片描述][SouthEast]

转载于:https://www.cnblogs.com/SiriusRen/p/6532141.html

[SouthEast]: /images/20211220/ead87bb765bf4b8a8fedba057dd4cf4c.png