首页 > 代码库 > POJ 1966：Cable TV Network（最小点割集）
POJ 1966：Cable TV Network（最小点割集）
http://poj.org/problem?id=1966
题意：给出一个由n个点，m条边组成的无向图。求最少去掉多少点才能使得图中存在两点，它们之间不连通。
思路：将点i拆成a和b，连一条a->b的容量为1的边，代表这个点只能走一次，然后如果点i和点j有边相连，那么将bi和aj相连，bj和ai相连，容量为INF，代表这条边可以走INF次。
然后O（n^2）枚举源点和汇点跑最大流，算的最小的最大流就是答案。（这个时候的最大流代表的是S跑到T需要经过多少路径（最小割），如果得到的最大流是INF，那么代表图完全连通，因此还要和n取一个较小值）。
有一个以前模板的点要完善：初始化 index = S;
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 #define N 210 6 #define INF 0x3f3f3f3f 7 struct Edge { 8 int v, nxt, cap, init; 9 Edge () {}10 Edge (int v, int nxt, int cap, int init) : v(v), nxt(nxt), cap(cap), init(init) {}11 } edge[N*N];12 int head[N], tot, dis[N], cur[N], pre[N], gap[N], n, m;13 14 void Add(int u, int v, int cap) {15 edge[tot] = Edge(v, head[u], cap, cap); head[u] = tot++;16 edge[tot] = Edge(u, head[v], 0, 0); head[v] = tot++;17 }18 19 int BFS(int S, int T) {20 queue<int> que; que.push(T);21 memset(dis, INF, sizeof(dis));22 memset(gap, 0, sizeof(gap));23 gap[0]++; dis[T] = 0;24 while(!que.empty()) {25 int u = que.front(); que.pop();26 for(int i = head[u]; ~i; i = edge[i].nxt) {27 int v = edge[i].v;28 if(dis[v] == INF) {29 dis[v] = dis[u] + 1;30 gap[dis[v]]++;31 que.push(v);32 }33 }34 }35 }36 37 int ISAP(int S, int T, int n) {38 BFS(S, T);39 memcpy(cur, head, sizeof(cur));40 int u = pre[S] = S, i, index, flow, ans = 0;41 while(dis[S] < n) {42 if(u == T) {43 flow = INF, index = S; // index = S !!!44 for(i = S; i != T; i = edge[cur[i]].v)45 if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;46 for(i = S; i != T; i = edge[cur[i]].v)47 edge[cur[i]].cap -= flow, edge[cur[i]^1].cap += flow;48 ans += flow, u = index;49 }50 for(i = cur[u]; ~i; i = edge[i].nxt)51 if(edge[i].cap > 0 && dis[edge[i].v] == dis[u] - 1) break;52 if(~i) {53 pre[edge[i].v] = u; cur[u] = i; u = edge[i].v;54 } else {55 if(--gap[dis[u]] == 0) break;56 int md = n;57 for(i = head[u]; ~i; i = edge[i].nxt)58 if(md > dis[edge[i].v] && edge[i].cap > 0) md = dis[edge[i].v], cur[u] = i;59 gap[dis[u] = md + 1]++;60 u = pre[u];61 }62 }63 return ans;64 }65 66 int main() {67 while(~scanf("%d%d", &n, &m)) {68 memset(head, -1, sizeof(head)); tot = 0;69 for(int i = 1; i <= n; i++) Add(i, i + n, 1);70 for(int i = 1; i <= m; i++) {71 int u, v; scanf(" (%d, %d)", &u, &v);72 u++, v++;73 Add(u + n, v, INF); Add(v + n, u, INF);74 }75 int ans = INF;76 for(int i = 1; i < n; i++) {77 for(int j = i + 1; j <= n; j++) {78 for(int k = 0; k < tot; k++) edge[k].cap = edge[k].init;79 int now = ISAP(i + n, j, 2 * n);80 if(now < ans) ans = now;81 }82 }83 if(ans > n) ans = n;84 printf("%d\n", ans);85 }86 return 0;87 }
POJ 1966：Cable TV Network（最小点割集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。