首页 > 代码库 > UVa 1660 电视网络（点连通度+最小割最大流+Dinic）
UVa 1660 电视网络（点连通度+最小割最大流+Dinic）
https://vjudge.net/problem/UVA-1660
题意：
给出一个无向图，求出点连通度。即最少删除多少个点，使得图不连通。
思路：
如果求线连通度的话，直接求个最大流就可以了。但这题我们删除的是点，用拆点法来使点具有流量的性质，把每个点都拆分为两个点，容量为1，表示可以使用一次。然后，题目中给出的连通的点之间的容量设为INF，因为我们不是要删除这两点之间的线。
最后，我们固定一个源点，枚举汇点，找到最小的删除数。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<string> 5 #include<vector> 6 #include<queue> 7 using namespace std; 8 9 const int maxn = 105; 10 const int INF = 0x3f3f3f3f; 11 12 struct Edge 13 { 14 int from,to, cap, flow; 15 Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){} 16 }; 17 18 int n, m,t; 19 vector<Edge> edges; 20 vector<Edge> edge; 21 vector<int> G[maxn]; 22 int vis[maxn]; 23 int d[maxn]; //从起点到i的距离 24 int cur[maxn]; //当前弧下标 25 int flow; 26 27 void init() 28 { 29 for (int i = 0; i < maxn; i++) 30 G[i].clear(); 31 edges.clear(); 32 } 33 34 void AddEdge(int from, int to, int cap) 35 { 36 edges.push_back(Edge(from, to, cap, 0)); 37 edges.push_back(Edge(to, from, 0, 0)); 38 int m = edges.size(); 39 G[from].push_back(m - 2); 40 G[to].push_back(m - 1); 41 } 42 43 44 int BFS(int s,int t) 45 { 46 memset(vis, 0, sizeof(vis)); 47 memset(d, 0, sizeof(d)); 48 queue<int> Q; 49 Q.push(s); 50 d[s] = 0; 51 vis[s] = 1; 52 while (!Q.empty()) 53 { 54 int x = Q.front(); 55 Q.pop(); 56 for (int i = 0; i < G[x].size(); i++) 57 { 58 Edge& e = edges[G[x][i]]; 59 if (!vis[e.to] && e.cap>e.flow) 60 { 61 vis[e.to] = 1; 62 d[e.to] = d[x] + 1; 63 Q.push(e.to); 64 } 65 } 66 } 67 return vis[t]; 68 } 69 70 int DFS(int x,int t,int a) 71 { 72 if (x == t || a == 0) return a; 73 int flow = 0, f; 74 for (int& i = cur[x]; i < G[x].size(); i++) 75 { 76 Edge& e = edges[G[x][i]]; 77 if (d[x] + 1 == d[e.to] && (f = DFS(e.to,t ,min(a,e.cap - e.flow)))>0) 78 { 79 e.flow += f; 80 edges[G[x][i] ^ 1].flow -= f; 81 flow += f; 82 a -= f; 83 if (a == 0) break; 84 } 85 } 86 return flow; 87 } 88 89 void Maxflow(int s,int t) 90 { 91 flow = 0; 92 while (BFS(s,t)) 93 { 94 memset(cur, 0, sizeof(cur)); 95 flow += DFS(s, t,INF); 96 } 97 } 98 99 int main()100 {101 //freopen("D:\\txt.txt", "r", stdin);102 int x,y;103 while (~scanf("%d%d",&n,&m))104 {105 init();106 for (int i = 1; i < n; i++)107 AddEdge(i, i + n, 1);108 for (int i = 0; i < m; i++)109 {110 scanf(" (%d,%d)", &x, &y);111 AddEdge(x + n, y, INF);112 AddEdge(y + n, x, INF);113 }114 edge = edges;115 flow = 0;116 int ans = n;117 for (int i = 1; i < n; i++)118 {119 edges = edge; //这个不能忘120 Maxflow(n, i); //0为源点，因为前面都加了n，所以这里0也要加上n121 ans = min(ans, flow);122 }123 printf("%d\n",ans);124 }125 }
UVa 1660 电视网络（点连通度+最小割最大流+Dinic）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。