首页 > 代码库 > HDU 3488 Tour【多个环的并】
HDU 3488 Tour【多个环的并】
大意：告诉你一些国家和一些单项路，每条路连接两个国家，告诉你之间的距离，现在要使每个国家都在一个环中
求最小距离
分析：这是做过的第二个多个环的并的问题
每个点的入读和出度都为1
把n个点拆点
由于二分图最优匹配的性质可知每个点都会出现在匹配中
相当于每个点出现一次
左边为出度点 有边为入读点
值得注意的是两个国家可能会有多条路
要选取最短的
----想起东北赛死在这上边了 ----全都是泪啊
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 205; 9 const int INF = 1000000000; 10 11 struct KM { 12 int n; 13 vector<int> G[maxn]; 14 int W[maxn][maxn]; 15 int Lx[maxn], Ly[maxn]; 16 int Left[maxn]; 17 bool S[maxn], T[maxn]; 18 19 void init(int n) { 20 this -> n = n; 21 for(int i = 0; i <= n; i++) G[i].clear(); 22 memset(W, 0, sizeof(W)); 23 } 24 25 void AddEdge(int u, int v, int w) { 26 if(W[u][v] == 0) { 27 G[u].push_back(v); 28 W[u][v] = -w; 29 } else if(w < - W[u][v]) { 30 W[u][v] = -w; 31 } 32 } 33 34 bool match(int u) { 35 S[u] = true; 36 for(int i = 0; i < G[u].size(); i++) { 37 int v = G[u][i]; 38 if(Lx[u] + Ly[v] == W[u][v] && !T[v]) { 39 T[v] = true; 40 if(Left[v] == -1 || match(Left[v])) { 41 Left[v] = u; 42 return true; 43 } 44 } 45 } 46 return false; 47 } 48 49 void update() { 50 int a = INF; 51 for(int u = 1; u <= n; u++) if(S[u]) 52 for(int i = 0; i < G[u].size(); i++) { 53 int v = G[u][i]; 54 if(!T[v]) a = min(a, Lx[u] + Ly[v] - W[u][v]); 55 } 56 for(int i = 1; i <= n; i++) { 57 if(S[i]) Lx[i] -= a; 58 if(T[i]) Ly[i] += a; 59 } 60 } 61 62 int solve() { 63 for(int i = 1; i <= n; i++) { 64 Left[i] = -1; 65 Ly[i] = 0; 66 Lx[i] = 0; 67 for(int j = 1; j <= n; j++) { 68 if(W[i][j] != INF) { 69 Lx[i] = max(Lx[i], W[i][j]); 70 } 71 } 72 } 73 for(int u = 1; u <= n; u++) { 74 for(; ;) { 75 for(int i = 1; i <= n; i++) S[i] = T[i] = false; 76 if(match(u)) break; else update(); 77 } 78 } 79 int ans = 0; 80 for(int i = 1; i <= n; i++) { 81 ans += Lx[i] + Ly[i]; 82 } 83 return ans; 84 } 85 }; 86 87 KM g; 88 89 int main() { 90 int t; 91 int n, m; 92 int u, v, w; 93 scanf("%d",&t); 94 while(t--) { 95 scanf("%d %d",&n, &m); 96 g.init(n); 97 while(m--) { 98 scanf("%d %d %d",&u, &v, &w); 99 g.AddEdge(u, v, w );100 }101 printf("%d\n", -g.solve()) ;102 }103 return 0;104 }
HDU 3488 Tour【多个环的并】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。