Description

在一些一對一游戲的比賽（如下棋、乒乓球和羽毛球的單打）中，我們經(jīng)常會遇到A勝過B，B勝過C而C又勝過A的有趣情況，不妨形象的稱之為剪刀石頭布情況。有的時候，無聊的人們會津津樂道于統(tǒng)計有多少這樣的剪刀石頭布情況發(fā)生，即有多少對無序三元組(A, B, C)，滿足其中的一個人在比賽中贏了另一個人，另一個人贏了第三個人而第三個人又勝過了第一個人。注意這里無序的意思是說三元組中元素的順序并不重要，將(A, B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B, A)視為相同的情況。 有N個人參加一場這樣的游戲的比賽，賽程規(guī)定任意兩個人之間都要進行一場比賽：這樣總共有場比賽。比賽已經(jīng)進行了一部分，我們想知道在極端情況下，比賽結(jié)束后最多會發(fā)生多少剪刀石頭布情況。即給出已經(jīng)發(fā)生的比賽結(jié)果，而你可以任意安排剩下的比賽的結(jié)果，以得到盡量多的剪刀石頭布情況。

Input

輸入文件的第1行是一個整數(shù)N，表示參加比賽的人數(shù)。 之后是一個N行N列的數(shù)字矩陣：一共N行，每行N列，數(shù)字間用空格隔開。 在第(i+1)行的第j列的數(shù)字如果是1，則表示i在已經(jīng)發(fā)生的比賽中贏了j；該數(shù)字若是0，則表示在已經(jīng)發(fā)生的比賽中i敗于j；該數(shù)字是2，表示i和j之間的比賽尚未發(fā)生。數(shù)字矩陣對角線上的數(shù)字，即第(i+1)行第i列的數(shù)字都是0，它們僅僅是占位符號，沒有任何意義。 輸入文件保證合法，不會發(fā)生矛盾，當i≠j時，第(i+1)行第j列和第(j+1)行第i列的兩個數(shù)字要么都是2，要么一個是0一個是1。

Output

輸出文件的第1行是一個整數(shù)，表示在你安排的比賽結(jié)果中，出現(xiàn)了多少剪刀石頭布情況。 輸出文件的第2行開始有一個和輸入文件中格式相同的N行N列的數(shù)字矩陣。第(i+1)行第j個數(shù)字描述了i和j之間的比賽結(jié)果，1表示i贏了j，0表示i負于j，與輸入矩陣不同的是，在這個矩陣中沒有表示比賽尚未進行的數(shù)字2；對角線上的數(shù)字都是0。輸出矩陣要保證合法，不能發(fā)生矛盾。 題解：http://blog.csdn.net/pouy94/article/details/5972444 PS：這題太牛叉了值得一做…… 代碼（896MS）： 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 const int MAXN = 110; 9 const int MAXV = MAXN * MAXN; 10 const int MAXE = MAXN * MAXV; 11 const int INF = 0x7f7f7f7f; 12 13 struct ZWK_FLOW { 14 int head[MAXV], dis[MAXV]; 15 int to[MAXE], next[MAXE], flow[MAXE], cost[MAXE]; 16 int n, ecnt, st, ed; 17 18 void init() { 19 memset(head, 0, sizeof(head)); 20 ecnt = 2; 21 } 22 23 void add_edge(int u, int v, int c, int w) { 24 to[ecnt] = v; flow[ecnt] = c; cost[ecnt] = w; next[ecnt] = head[u]; head[u] = ecnt++; 25 to[ecnt] = u; flow[ecnt] = 0; cost[ecnt] = -w; next[ecnt] = head[v]; head[v] = ecnt++; 26 //printf("%d %d %d %d\n", u, v, c, w); 27 } 28 29 void spfa() { 30 for(int i = 1; i <= n; ++i) dis[i] = INF; 31 priority_queue<pair<int, int> > que; 32 dis[st] = 0; que.push(make_pair(0, st)); 33 while(!que.empty()) { 34 int u = que.top().second, d = -que.top().first; que.pop(); 35 if(d != dis[u]) continue; 36 for(int p = head[u]; p; p = next[p]) { 37 int &v = to[p]; 38 if(flow[p] && dis[v] > d + cost[p]) { 39 dis[v] = d + cost[p]; 40 que.push(make_pair(-dis[v], v)); 41 } 42 } 43 } 44 int t = dis[ed]; 45 for(int i = 1; i <= n; ++i) dis[i] = t - dis[i]; 46 } 47 48 int minCost, maxFlow; 49 bool vis[MAXV]; 50 51 int add_flow(int u, int aug) { 52 if(u == ed) { 53 maxFlow += aug; 54 minCost += dis[st] * aug; 55 return aug; 56 } 57 vis[u] = true; 58 int now = aug; 59 for(int p = head[u]; p; p = next[p]) { 60 int &v = to[p]; 61 if(flow[p] && !vis[v] && dis[u] == dis[v] + cost[p]) { 62 int t = add_flow(v, min(now, flow[p])); 63 flow[p] -= t; 64 flow[p ^ 1] += t; 65 now -= t; 66 if(!now) break; 67 } 68 } 69 return aug - now; 70 } 71 72 bool modify_label() { 73 int d = INF; 74 for(int u = 1; u <= n; ++u) if(vis[u]) { 75 for(int p = head[u]; p; p = next[p]) { 76 int &v = to[p]; 77 if(flow[p] && !vis[v]) d = min(d, dis[v] + cost[p] - dis[u]); 78 } 79 } 80 if(d == INF) return false; 81 for(int i = 1; i <= n; ++i) if(vis[i]) dis[i] += d; 82 return true; 83 } 84 85 int min_cost_flow(int ss, int tt, int nn) { 86 st = ss, ed = tt, n = nn; 87 minCost = maxFlow = 0; 88 spfa(); 89 while(true) { 90 while(true) { 91 for(int i = 1; i <= n; ++i) vis[i] = false; 92 if(!add_flow(st, INF)) break; 93 } 94 if(!modify_label()) break; 95 } 96 return minCost; 97 } 98 } G; 99 100 int n, m; 101 int mat[MAXN][MAXN], ans[MAXN][MAXN]; 102 103 inline int encode(int i, int j) { 104 if(i > j) swap(i, j); 105 return i * n + j; 106 } 107 108 int main() { 109 scanf("%d", &n); 110 for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &mat[i][j]); 111 m = n * n; 112 int ss = n + m + 1, tt = ss + 1; 113 G.init(); 114 int sum = n * (n - 1) * (n - 2) / 6; 115 for(int i = 1; i <= n; ++i) { 116 for(int j = 1, tmp = 1; j < n; ++j, tmp += 2) G.add_edge(ss, i, 1, tmp); 117 for(int j = 1; j <= n; ++j) if(mat[i][j] != 0) 118 ans[i][j] = G.ecnt, G.add_edge(i, encode(i, j), 1, 0); 119 } 120 for(int i = 1; i <= m; ++i) G.add_edge(i + n, tt, 1, 0); 121 int x = G.min_cost_flow(ss, tt, tt); 122 printf("%d\n", sum - (x - n * (n - 1) / 2) / 2); 123 for(int i = 1; i <= n; ++i) { 124 for(int j = 1; j <= n; ++j) { 125 if(j != 1) printf(" "); 126 if(mat[i][j] != 2) printf("%d", mat[i][j]); 127 else { 128 if(G.flow[ans[i][j]] == 0) printf("1"); 129 else printf("0"); 130 } 131 } 132 puts(""); 133 } 134 } View Code

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/oyking/p/3330462.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2597 剪刀石头布（最小费用最大流）（WC2007）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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