POJ 1966 Cable TV Network

网络流，连通度问题

传送门：POJ

---

题意

无向图，求点连通度，即最少去掉多少个点使得图不连通。注意一个点的图被视为连通，需要将那个点去掉。

---

思路

关于连通度问题：参见。

其实图的连通度分为有向图无向图、点连通度边连通度，共四种。

基础是有向图边连通度，就是将原图边容量定为1，随便找一源点，枚举汇点跑网络流。证明见参见。

对于无向图，比如a与b有容量为10的边，添加a到b与b到a两条边，容量都是10。

对于点连通性，稍微复杂一些。不过想到可以用无穷大的边防止被割，所以拆点建图。内部容量1，割了边表示割去点。其余容量无穷。详细加边方式见代码。然后枚举时注意，拆点两点假设是添加了一个后点到前点的边。枚举时需要任意前点作为源，枚举的汇点从后点里面枚举。

另外有两点注意。为了避免重复建图，枚举跑网络流时需要清空流量。见代码maxflow函数内部。然后如果跑出的流大于点数，要么这是个完全图(原因我不知道，但完全图跑出来流是无穷)，要么有重边(我觉得有重边跑出来也可能大于n)。这时候直接把流置为n就行了。

ps：关于重边，我不确定。但是我把最后条件由if(n*(n-1)/2>=m||ma>n)改为if(n*(n-1)/2>=m) 是WA的，而if(ma>n)是能过的。

---

代码

#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> using namespace std; const int MAXN=3007; const int oo=0x3f3f3f3f; const long long int loo=9223372036854775807ll; typedef long long LL; struct Dinic { struct Edge{ int from, to, cap, flow;//cap容量 flow流量 Edge(){} Edge(int u, int v, int c, int f){ from=u;to=v;cap=c;flow=f; } }; vector<Edge> edges;//顺序的插入边 vector<int> G[MAXN];//保存边号 bool vis[MAXN];//BFS使用 int d[MAXN]; int cur[MAXN]; void init(int n) { for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0));//单向边第三个参数写0，双向边写cap int t_m=edges.size(); G[from].push_back(t_m-2); G[to].push_back(t_m-1); } bool BFS(int s, int t) { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow)//残量网络 { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a, int s, int t) { if(x==t||a==0) return a; int flow=0, _f; for(int& i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(_f=DFS(e.to, min(a, e.cap-e.flow), s, t))>0) { e.flow+=_f; edges[G[x][i]^1].flow-=_f; flow+=_f; a-=_f; if(a==0) break; } } return flow; } int Maxflow(int s, int t) { for(int i=0;i<edges.size();i++) { edges[i].flow=0;//每次重置流量 } int flow=0; while(BFS(s, t)) { memset(cur, 0, sizeof(cur)); flow+=DFS(s, oo, s, t); } return flow; } }; int main() { int m,n; while(cin>>n>>m)//n点数m边数 { Dinic dinic; dinic.init(n); if(m==0) cout<<((n==1) ? '1' : '0')<<endl; else { const int s=n; for(int i=0;i<n;i++) dinic.AddEdge(i, i+n, 1); for(int i=0;i<m;i++) { char ss[100]; scanf("%s", ss); int a, b; sscanf(ss,"%*c%d%*c%d%*c", &a, &b); dinic.AddEdge(a+n, b, oo);dinic.AddEdge(b+n, a, oo); } int ma=oo; for(int i=1;i<n;i++) { ma=min(ma, dinic.Maxflow(s, i)); } if(ma>n) ma=n; cout<<ma<<endl; } } //system("pause"); return 0; }