hdu 3435 A new Graph Game

http://acm.hdu.edu.cn/showproblem.php?pid=3435

　　题意是，从一个给定的图里得到一个或以上的哈密顿回路，使得所有边权之和最小。子图不能只有一个点。

　　很容易想到用KM最优匹配，将自环全都设置为不连通，然后一次KM匹配就可以完成了！这次的KM算法不能只用一个slack来记录松弛的大小，必须要用多个slack，以空间来换时间。于是我就顺便更新我的KM模板了~！

AC代码：

View Code

  1 /*
  2  * Author: Lyon
  3  * Problem: hdu 3435
  4  */
  5 
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <cassert>
  9 #include <algorithm>
 10 
 11 using namespace std;
 12 const int inf = 100000000;
 13 const int maxn = 1001;
 14 
 15 int lx[maxn], ly[maxn], mat[maxn][maxn], match[maxn];
 16 bool vx[maxn], vy[maxn];
 17 //int slack;
 18 int sl[maxn];
 19 
 20 bool dfs(int x, int n){
 21     vx[x] = true;
 22     for (int y = 1; y <= n; y++){
 23         if (vy[y]) continue;
 24 
 25         int t = lx[x] + ly[y] - mat[x][y];
 26 
 27         if (t){
 28             //slack = min(slack, t);
 29             sl[y] = min(sl[y], t);
 30         }
 31         else{
 32             vy[y] = true;
 33             if (~match[y] && !dfs(match[y], n)) continue;
 34             match[y] = x;
 35 
 36             return true;
 37         }
 38     }
 39 
 40     return false;
 41 }
 42 
 43 int km(int n){
 44     for (int i = 1; i <= n; i++){
 45         match[i] = -1;
 46         lx[i] = -inf;
 47         ly[i] = 0;
 48         for (int j = 1; j <= n; j++){
 49             lx[i] = max(lx[i], mat[i][j]);
 50         }
 51     }
 52     for (int x = 1; x <= n; x++){
 53         for (int i = 1; i <= n; i++){
 54             sl[i] = inf;
 55         }
 56 
 57         int minsl;
 58 
 59         while (true){
 60             for (int i = 1; i <= n; i++){
 61                 vx[i] = vy[i] = false;
 62             }
 63             //slack = inf;
 64             if (dfs(x, n)) break;
 65             minsl = inf;
 66             for (int i = 1; i <= n; i++){
 67                 if (!vy[i]) minsl = min(minsl, sl[i]);
 68             }
 69             for (int i = 1; i <= n; i++){
 70                 if (vx[i]) lx[i] -= minsl;
 71                 if (vy[i]) ly[i] += minsl;
 72                 else sl[i] -= minsl;
 73             }
 74             /*
 75             for (int i = 1; i <= n; i++){
 76                 if (vx[i]) lx[i] -= slack;
 77                 if (vy[i]) ly[i] += slack;
 78             }
 79             */
 80         }
 81     }
 82 
 83     int ret = 0;
 84 
 85     for (int i = 1; i <= n; i++){
 86         if (~match[i]) ret += mat[match[i]][i];
 87         if (ret <= -inf) return -1;
 88     }
 89 
 90     return -ret;
 91 }
 92 
 93 void makeGraph(int n, int m){
 94     for (int i = 1; i <= n; i++){
 95         for (int j = 1; j <= n; j++){
 96             mat[i][j] = -inf;
 97         }
 98     }
 99     while (m--){
100         int a, b, c;
101 
102         scanf("%d%d%d", &a, &b, &c);
103         if (a == b) continue;
104         mat[a][b] = mat[b][a] = max(-c, mat[a][b]);
105     }
106 }
107 
108 int main(){
109     int n, m, T;
110 
111     scanf("%d", &T);
112     for (int i = 1; i <= T; i++){
113         scanf("%d%d", &n, &m);
114         makeGraph(n, m);
115 
116         int ans = km(n);
117 
118         printf("Case %d: ", i);
119         if (~ans){
120             printf("%d\n", ans);
121         }
122         else puts("NO");
123     }
124 
125     return 0;
126 }

——written by Lyon