题目：http://poj.org/problem?id=1966
把一个点拆成入点和出点，之间连一条边权为1的边，跑最大流即最小割；
原始的边权赋成inf防割；
枚举源点和汇点，直接相邻的两个点不必枚举；
注意：1、源点为枚举点i的出点，汇点为枚举点j的入点；
2、读入方式，免空格；
3、在dinic跑最大流的过程中，会改变边权，因此每次枚举都要复制一组边跑最大流，以免影响后面；
另：数据中的点从0开始，所以读入的时候++来使用。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;queue<int>q;int n,m,head[105],cur[105],ct=1,inf=1e9,ans,d[105];bool sid[55][55];struct N{ ???int to,next,w; ???N(int t=0,int n=0,int ww=0):to(t),next(n),w(ww) {}}edge[6005],ed[6005];void add(int x,int y,int z){ ???ed[++ct]=N(y,head[x],z);head[x]=ct; ???ed[++ct]=N(x,head[y],0);head[y]=ct;}bool bfs(int s,int t){ ???memset(d,0,sizeof d); ???while(q.size())q.pop(); ???d[s]=1;q.push(s); ???while(q.size()) ???{ ???????int x=q.front();q.pop(); ???????for(int i=head[x];i;i=edge[i].next) ???????{ ???????????int u=edge[i].to; ???????????if(!d[u]&&edge[i].w) ???????????{ ???????????????d[u]=d[x]+1; ???????????????q.push(u); ???????????} ???????} ???} ???return d[t];}int dfs(int x,int f,int t){ ???if(x==t)return f; ???int res=0; ???for(int i=cur[x];i;i=edge[i].next) ???{ ???????int u=edge[i].to; ???????if(d[u]==d[x]+1&&edge[i].w) ???????{ ???????????int tmp=dfs(u,min(edge[i].w,f-res),t); ???????????edge[i].w-=tmp; ???????????edge[i^1].w+=tmp; ???????????res+=tmp; ???????????if(edge[i].w)cur[x]=i; ???????????if(res==f)return f; ???????} ???} ???if(!res)d[x]=0; ???return res;}int dinic(int s,int t){ ???memcpy(edge,ed,sizeof ed);//!!! ???int res=0; ???while(bfs(s+n,t)) ???{ ???????for(int i=0;i<=2*n;i++)cur[i]=head[i]; ???????res+=dfs(s+n,inf,t); ???} ???return res;}int main(){ ???while(scanf("%d%d",&n,&m)==2) ???{ ???????if(!n||n==1) ???????{ ???????????printf("%d\n",n); ???????????continue; ???????} ???????if(!m) ???????{ ???????????printf("0\n"); ???????????continue; ???????} ???????ct=1;ans=inf; ???????memset(head,0,sizeof head); ???????memset(sid,0,sizeof sid); ???????for(int i=1;i<=n;i++)add(i,i+n,1);// ???????char dc=0; ???????for(int i=1;i<=m;i++) ???????{// ???????????dc=0;// ???????????while(dc!=‘(‘)scanf("%c",&dc); ???????????int x,y; ???????????scanf(" (%d,%d)",&x,&y);//或者采用注释方法读入，这里为 scanf("%d,%d",&x,&y); ???????????x++;y++;// ???????????sid[x][y]=1;sid[y][x]=1; ???????????add(x+n,y,inf); ???????????add(y+n,x,inf); ???????} ???????for(int i=1;i<=n;i++) ???????????for(int j=i+1;j<=n;j++) ???????????????if(!sid[i][j])ans=min(ans,dinic(i,j)); ???????if(ans==inf)ans=n; ???????printf("%d\n",ans);// ???????dc=0;// ???????while(dc!=‘)‘)scanf("%c",&dc); ???} ???return 0;}poj1966Cable TV Network——无向图最小割(最大流)
原文地址：https://www.cnblogs.com/Zinn/p/8620780.html