首页 > 代码库 > ZOJ 2182 Cable TV Network（无向图点割-最大流）

ZOJ 2182 Cable TV Network（无向图点割-最大流）

2024-07-09 00:24:34   222人阅读

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2182

题意：给出一个无向图，问最少删掉多少个顶点之后图变得不连通？

思路：将原图每个点拆点(i,i+n)，连边<i,i+n,1>，对原图的边(u,v)，连边<u+n,v,INF>,<v+n,u,INF>。然后对于每对顶点(i,j)跑最大流(i+n,j)。所有最大流的最小值即为答案。

 

struct node{    int v,cap,next;};node edges[N*10];int head[N],e;int curedge[N],h[N],num[N],pre[N];int s,t;void add(int u,int v,int cap){    edges[e].v=v;    edges[e].cap=cap;    edges[e].next=head[u];    head[u]=e++;}void Add(int u,int v,int cap){    add(u,v,cap);    add(v,u,0);}int Maxflow(int s,int t,int n){    clr(h,0); clr(num,0);    int i;    FOR0(i,n+1) curedge[i]=head[i];    int u=s,Min,k,x,ans=0;    while(h[u]<n)    {        if(u==t)        {            Min=INF*100;            for(i=s;i!=t;i=edges[curedge[i]].v)            {                x=curedge[i];                if(edges[x].cap<Min)                {                    Min=edges[x].cap;                    k=i;                }            }            ans+=Min; u=k;            for(i=s;i!=t;i=edges[curedge[i]].v)            {                x=curedge[i];                edges[x].cap-=Min;                edges[x^1].cap+=Min;            }        }        for(i=curedge[u];i!=-1;i=edges[i].next)        {            if(edges[i].cap>0&&h[u]==h[edges[i].v]+1)            {                break;            }        }        if(i!=-1)        {            curedge[u]=i;            pre[edges[i].v]=u;            u=edges[i].v;        }        else        {            if(--num[h[u]]==0) break;            curedge[u]=head[u];            x=n;            for(i=head[u];i!=-1;i=edges[i].next)            {                k=edges[i].v;                if(edges[i].cap>0&&h[k]<x) x=h[k];            }            h[u]=x+1; num[x+1]++;            if(u!=s) u=pre[u];        }    }    return ans;}int n,m;int a[55][55];int visit[55];void DFS(int u){    visit[u]=1;    int i,v;    FOR1(i,n) if(a[u][i]&&!visit[i])    {        DFS(i);    }}int ok(){    clr(visit,0);    DFS(1);    int i;    FOR1(i,n) if(!visit[i]) return 0;    return 1;}int cal(int s,int t){    clr(head,-1); e=0;    int i,j;    FOR1(i,n) Add(i,i+n,1);    FOR1(i,n) for(j=1;j<=n;j++) if(a[i][j])    {        Add(i+n,j,INF);    }    return Maxflow(s+n,t,n+n+2);}int get(){    int x=0;    char c=getchar();    while(!isdigit(c))c=getchar();    while(isdigit(c))     {        x=x*10+c-‘0‘;        c=getchar();    }    return x;}int main(){    while(scanf("%d%d",&n,&m)!=-1)    {        if(m==0)        {            if(n==0) puts("0");            else if(n==1) puts("1");            else puts("0");            continue;        }        clr(a,0);        int u,v,i;        FOR0(i,m)        {            u=get(); v=get();            a[u+1][v+1]=a[v+1][u+1]=1;        }                 if(!ok())        {            puts("0");            continue;        }        int j;        int ans=INF;        FOR1(i,n) for(j=1;j<=n;j++) if(i!=j)         {            int x=cal(i,j);            ans=min(ans,x);        }        if(ans==INF||ans==n-1) ans=n;        PR(ans);    }}

 

 


联系
我们