Description:
给定一张无向图，问至少去掉多少个点， 可以使图不连通。点数N ≤ 50
思路：先固定一个点s，然后枚举另一个点t，然后求最少要割掉几个点使两点不连通
自然联系到最小割，但最小割是割边，割点呢？只要把每个点拆成两个点，割去一个点等价于在网络中断开其拆成的两点中间的边。
所以将原无向图中的边权设为正无穷大，然后将每个点对之间的边权设为1，然后就能用最小割写了
#include<iostream>#include<cstring>#include<queue>#include<cstdio>using namespace std;const int N = 110;const int M = 10010;const int INF = 1e9;int head[N],now;struct edges{ ???int to,next,w;}edge[M<<1];void add(int u,int v,int w){ edge[++now] = {v,head[u],w}; head[u] = now;}int n,m,s,t,dep[N],ans;void init(){ ???memset(edge,0,sizeof(edge)); now = 1; ???memset(head,0,sizeof(head)); ???memset(dep,0,sizeof(dep));}int dinic(int x,int flow){ ???if(x == t) return flow; ???int rest = flow, k; ???for(int i = head[x]; i; i = edge[i].next){ ???????int v = edge[i].to; ???????if(edge[i].w && dep[v] == dep[x] + 1){ ???????????k = dinic(v,min(rest, edge[i].w)); ???????????if(!k) dep[v] = 0; ???????????edge[i].w -= k; ???????????edge[i ^ 1].w += k; ???????????rest -= k; ???????} ???} ???return flow - rest;}bool bfs(){ ???memset(dep,0,sizeof(dep)); ???queue<int> q; ???q.push(s); dep[s] = 1; ???while(!q.empty()){ ???????int x = q.front(); q.pop(); ???????for(int i = head[x]; i; i = edge[i].next){ ???????????int v = edge[i].to; ???????????if(edge[i].w && !dep[v]){ ???????????????q.push(v); ???????????????dep[v] = dep[x] + 1; ???????????????if(v == t) return 1; ???????????} ???????} ???} ???return 0;}struct input{ ???int x,y;}inp[M];int main(){ ???while(scanf("%d%d",&n,&m) != EOF){ ???????ans = INF; ???????int x,y; ???????for(int i = 1; i <= m; i++){ ???????????scanf(" (%d,%d)",&x,&y); ???????????x++, y++; ???????????inp[i] = {x,y};// ???????????add(x,y+n,INF);add(y+n,x,0); ???????} ???????if(n == 1){ ???????????puts("1"); ???????????continue; ???????} ???????s = 1; ???????for(t = 2; t <= n; t++){ ?//枚举一个终点 ????????????init(); ???????????for(int i = 1; i <= m; i++){ ???????????????add(inp[i].y + n,inp[i].x, INF); ?//拆点连边 ????????????????add(inp[i].x,inp[i].y + n, 0); ???????????????add(inp[i].x + n,inp[i].y, INF); ???????????????add(inp[i].y,inp[i].x + n, 0); ???????????} ???????????int x,y; ???????????for(int i = 1; i <= n; i++) ?????????????if(i != s && i != t) ???????????????add(i,i+n,1), add(i+n,i,0); ???//把所对拆点之间的边权设为1 ???????????int tmp = 0, maxflow = 0; ???????????s += n; ???????????while(bfs()) ?//最大流最小割 ??????????????while(tmp = dinic(s,INF)) maxflow += tmp; ???????????ans = min(ans,maxflow); ???????????s -= n; ???????} ???????if(ans == INF) printf("%d\n",n); ???????else printf("%d\n",ans); ???} ???return 0;}poj 1966 Cable TV Network
原文地址：https://www.cnblogs.com/Rorshach/p/8684500.html