?

題目傳送門

1 /* 2 KM： 相比HDOJ_1533，多了重邊的處理，還有完美匹配的判定方法 3 */ 4 #include <cstdio> 5 #include <cmath> 6 #include <algorithm> 7 #include <cstring> 8 using namespace std; 9 10 const int MAXN = 1e2 + 10; 11 const int INF = 0x3f3f3f3f; 12 int x[MAXN], y[MAXN]; 13 int w[MAXN][MAXN]; 14 int visx[MAXN], visy[MAXN]; 15 int ly[MAXN]; 16 int n, m, d; 17 18 bool DFS(int u) { 19 visx[u] = true; 20 for (int i=1; i<=n; ++i) { 21 if (!visy[i] && x[u] + y[i] == w[u][i]) { 22 visy[i] = true; 23 if (ly[i] == -1 || DFS (ly[i])) { 24 ly[i] = u; return true; 25 } 26 } 27 else if (x[u] + y[i] > w[u][i]) d = min (d, x[u] + y[i] - w[u][i]); 28 } 29 return false; 30 } 31 32 int KM(void) { 33 for (int i=1; i<=n; ++i) { 34 x[i] = -INF; 35 for (int j=1; j<=n; ++j) { 36 x[i] = max (x[i], w[i][j]); 37 } 38 } 39 40 memset (ly, -1, sizeof (ly)); 41 memset (y, 0, sizeof (y)); 42 for (int i=1; i<=n; ++i) { 43 while (true) { 44 memset (visx, false, sizeof (visx)); 45 memset (visy, false, sizeof (visy)); 46 d = INF; 47 if (DFS (i)) break; 48 for (int i=1; i<=n; ++i) { 49 if (visx[i]) x[i] -= d; 50 } 51 for (int j=1; j<=n; ++j) { 52 if (visy[j]) y[j] += d; 53 } 54 } 55 } 56 57 for (int i=1; i<=n; ++i) { 58 if (ly[i] == -1 || w[ly[i]][i] == -INF) return -1; 59 } 60 61 int res = 0; 62 for (int i=1; i<=n; ++i) { 63 res += x[i] + y[i]; 64 } 65 66 return -res; 67 } 68 69 int main(void) { //HDOJ 1853 Cyclic Tour 70 //freopen ("HDOJ_1853.in", "r", stdin); 71 72 while (scanf ("%d%d", &n, &m) == 2) { 73 if (!n && !m) break; 74 for (int i=1; i<=n; ++i) { 75 for (int j=1; j<=n; ++j) w[i][j] = -INF; 76 } 77 for (int i=1; i<=m; ++i) { 78 int u, v, c; scanf ("%d%d%d", &u, &v, &c); 79 if (-c > w[u][v]) w[u][v] = -c; 80 } 81 printf ("%d\n", KM ()); 82 } 83 84 return 0; 85 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/4662493.html

總結(jié)

以上是生活随笔為你收集整理的最大流增广路(KM算法) HDOJ 1853 Cyclic Tour的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。