题目：求一个无向图的点联通数，n<=50
思路：要删除一些点，让图不联通，关键是审视“不联通”这一概念。其实，不联通就是存在两个点没有路相连。可以考虑枚举两个点，问题就化简成了使两个点没有路。然而这个用最小割就很好做了，由于最小割模型是删除边的，所以把每个点拆成两点加一边，枚举的两个点分别为源点和汇点，跑最小割就行了。
我想到最小割后就一直在想怎么判联通。。。还是too young了
btw，大部分题解中只枚举一个点，这样做是不对的。比如说，你固定了源点，就默认了源点不能删，但恰好是删这个点最优呢？
给出hack数据：
3 2 (0,1) (0,2)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cassert> 5 #include<queue> 6 ?7 using namespace std; 8 ?9 const int N=100+3,M=3000+3;10 const int INF=0x3f3f3f3f;11 12 struct edge{13 ????int nxt,to,fl;14 }ed[M];15 16 int head[N],cur;17 int s,t;18 queue<int>q;19 int cap[N],fr[N];20 21 void add_edge(int l,int r,int f)22 {23 ????ed[cur]=(edge){head[l],r,f};24 ????head[l]=cur++;25 ????ed[cur]=(edge){head[r],l,0};26 ????head[r]=cur++;27 }28 29 int n,m;30 int get;31 bool ek()32 {33 ????memset(cap,0,sizeof(cap));34 ????cap[s]=INF;35 ????while(!q.empty())q.pop();36 ????q.push(s);37 ????while(!q.empty())38 ????{39 ????????int u=q.front();q.pop();40 ????????for(int i=head[u];i!=-1;i=ed[i].nxt)41 ????????????if(!cap[ed[i].to]&&ed[i].fl)42 ????????????????cap[ed[i].to]=min(cap[u],ed[i].fl),43 ????????????????fr[ed[i].to]=i,44 ????????????????q.push(ed[i].to);45 ????????if(cap[t])break;46 ????}47 ????if(!cap[t])return 0;48 ????get+=cap[t];49 ????for(int u=t;u!=s;u=ed[fr[u]^1].to)50 ????????ed[fr[u]].fl-=cap[t],51 ????????ed[fr[u]^1].fl+=cap[t];52 ????return 1;53 }54 55 56 57 int l[M],r[M];58 int main()59 {60 ????while(scanf("%d %d",&n,&m)!=EOF)61 ????{62 ????????for(int i=1;i<=m;i++)63 ????????????scanf(" (%d,%d)",&l[i],&r[i]);64 ????????int ans=n;65 ????????for(s=0;s<n;s++)66 ????????????for(t=s+1;t<n;t++)67 ????????????{68 ????????????????memset(head,0xff,sizeof(head));69 ????????????????cur=0;70 ????????????????get=0;71 ????????????????for(int i=1;i<=m;i++)72 ????????????????????add_edge(l[i],r[i]+n,n),73 ????????????????????add_edge(r[i],l[i]+n,n);74 ????????????????for(int i=0;i<n;i++)75 ????????????????????if(i==t||i==s)76 ????????????????????????add_edge(i+n,i,n);77 ????????????????????else78 ????????????????????????add_edge(i+n,i,1);79 ????????????????while(ek());80 ????????????????ans=min(ans,get);81 ????????????}82 ????????cout<<ans<<endl;83 ????}84 ????return 0;85 }[] [最小割]Cable TV Network UVA - 1660 POJ - 1966
原文地址：https://www.cnblogs.com/mgnfcnt/p/8728968.html