cms网站后台模版,东莞网页开发,名站在线,深圳定制网站制作Description 在一些一对一游戏的比赛#xff08;如下棋、乒乓球和羽毛球的单打#xff09;中#xff0c;我们经常会遇到A胜过B#xff0c;B胜过C而C又胜过A的有趣情况#xff0c;不妨形象的称之为剪刀石头布情况。有的时候#xff0c;无聊的人们会津津乐道于统计有多少这… Description 在一些一对一游戏的比赛如下棋、乒乓球和羽毛球的单打中我们经常会遇到A胜过BB胜过C而C又胜过A的有趣情况不妨形象的称之为剪刀石头布情况。有的时候无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生即有多少对无序三元组(A, B, C)满足其中的一个人在比赛中赢了另一个人另一个人赢了第三个人而第三个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要将(A, B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B, A)视为相同的情况。 有N个人参加一场这样的游戏的比赛赛程规定任意两个人之间都要进行一场比赛这样总共有场比赛。比赛已经进行了一部分我们想知道在极端情况下比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果而你可以任意安排剩下的比赛的结果以得到尽量多的剪刀石头布情况。 Input 输入文件的第1行是一个整数N表示参加比赛的人数。 之后是一个N行N列的数字矩阵一共N行每行N列数字间用空格隔开。 在第(i1)行的第j列的数字如果是1则表示i在已经发生的比赛中赢了j该数字若是0则表示在已经发生的比赛中i败于j该数字是2表示i和j之间的比赛尚未发生。数字矩阵对角线上的数字即第(i1)行第i列的数字都是0它们仅仅是占位符号没有任何意义。 输入文件保证合法不会发生矛盾当i≠j时第(i1)行第j列和第(j1)行第i列的两个数字要么都是2要么一个是0一个是1。 Output 输出文件的第1行是一个整数表示在你安排的比赛结果中出现了多少剪刀石头布情况。 输出文件的第2行开始有一个和输入文件中格式相同的N行N列的数字矩阵。第(i1)行第j个数字描述了i和j之间的比赛结果1表示i赢了j0表示i负于j与输入矩阵不同的是在这个矩阵中没有表示比赛尚未进行的数字2对角线上的数字都是0。输出矩阵要保证合法不能发生矛盾。 题解http://blog.csdn.net/pouy94/article/details/5972444 PS这题太牛叉了值得一做…… 代码896MS 1 #include cstdio2 #include cstring3 #include iostream4 #include algorithm5 #include queue6 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_queuepairint, 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 转载于:https://www.cnblogs.com/oyking/p/3330462.html
