Cable TV Network UVA - 1660(网络流拆点)

本文主要是介绍Cable TV Network UVA - 1660(网络流拆点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

n个点，然后给出m条边，然后问删至少多少个点可以得到不连通的图。

思路

不连通的图，把一个分成两个连通图是删点最少的情况，然后就联想到网络流最小割问题，最小割是删边，这个是删点，所以可以把一个点一切两开中间放一条边。然后任选一个点为起点，枚举其他的作为汇点，跑n-1次Dinic取最小值就行了。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 200;
struct Edge {int v, cap, nxt;
};
int n, m;
int head[maxn],tot;
Edge edges[maxn*maxn];
void init() {tot=0;memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int cap) {edges[tot].v = v, edges[tot].cap = cap, edges[tot].nxt = head[u], head[u] = tot++;edges[tot].v = u, edges[tot].cap = 0, edges[tot].nxt = head[v], head[v] = tot++;   
}
int d[maxn];
bool bfs(int s, int t) {memset(d, -1, sizeof(d));queue<int>q;d[s]=0;q.push(s); while(!q.empty()) {int u = q.front(); q.pop();if(u == t) return true;for(int e = head[u]; ~e; e = edges[e].nxt) {int &v = edges[e].v, cap = edges[e].cap;if(d[v] == -1 && cap > 0) {d[v] = d[u] + 1;q.push(v);}  }}return 0;
}
int dfs(int s, int t, int flow) {if(s == t) return flow;int pre = 0;for(int e = head[s]; ~e; e = edges[e].nxt) {int & v = edges[e].v, cap = edges[e].cap;if(d[v] == d[s] + 1 && cap > 0) {int tmp = min(flow-pre, cap);int tf = dfs(v, t, tmp);edges[e].cap -= tf;edges[e^1].cap += tf;pre += tf;if(pre == flow) return pre;}}return pre;
}
int dinic(int s, int t) {int ret = 0;while(bfs(s, t)) ret += dfs(s,t,inf);return ret;
}
vector<pair<int, int> > vecp;
Edge tmp[maxn*maxn];
int main()
{// freopen("/Users/maoxiangsun/MyRepertory/acm/i.txt", "r", stdin);while(~scanf("%d%d", &n, &m)) {init();for(int i = 1; i < n; i++) addEdge(i, i+n, 1);for(int i = 1; i <= m; i++) {int u, v;scanf(" (%d,%d)", &u, &v);addEdge(u+n, v, inf);addEdge(v+n, u, inf);}int ans = n;int S = n;memcpy(tmp, edges, sizeof(tmp));for(int T = 1; T < n; T++) {memcpy(edges, tmp, sizeof(tmp));ans = min(ans, dinic(S,T));}printf("%d\n", ans);}return 0;
}
/*
0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)
*/