Description
在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到A胜过B，B胜过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个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。
输入文件的第1行是一个整数N，表示参加比赛的人数。
之后是一个N行N列的数字矩阵：一共N行，每行N列，数字间用空格隔开。
在第(i+1)行的第j列的数字如果是1，则表示i在已经发生的比赛中赢了j；该数字若是0，则表示在已经发生的比赛中i败于j；该数字是2，表示i和j之间的比赛尚未发生。数字矩阵对角线上的数字，即第(i+1)行第i列的数字都是0，它们仅仅是占位符号，没有任何意义。
输入文件保证合法，不会发生矛盾，当i≠j时，第(i+1)行第j列和第(j+1)行第i列的两个数字要么都是2，要么一个是0一个是1。
Output
输出文件的第1行是一个整数，表示在你安排的比赛结果中，出现了多少剪刀石头布情况。
输出文件的第2行开始有一个和输入文件中格式相同的N行N列的数字矩阵。第(i+1)行第j个数字描述了i和j之间的比赛结果，1表示i赢了j，0表示i负于j，与输入矩阵不同的是，在这个矩阵中没有表示比赛尚未进行的数字2；对角线上的数字都是0。输出矩阵要保证合法，不能发生矛盾。
3
0 1 2
0 0 2
2 2 0
Sample Output
1
0 1 0
0 0 1
1 0 0
HINT
100%的数据中，N≤ 100。
Solution
费用流
可以根据胜负关系建立一张有向图。假设三个人中没出现石头剪刀布的情况，那么一定有一个人有两个入边。
记di为第i个人的入度，没出现的次数为∑ C(di,2)
题目即求Max{C(n,3)-∑ C(di,2)}的一种方案。
即Max{C(n,3) + 1/2∑di – 1/2∑di^2}。
其实∑di是定值，我们只需要求Min{∑di^2}即可。
最小化平方之类的东西，考虑费用递增。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int S, T, n;
const int INF = 1009999999;
inline int getint() {
int r = 0, k = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
namespace MIC {
const int N = 200005;
struct edge_type { int to, next, r, c; } edge[N<<1];
int h[N], cnte = 1;
void ins(const int u, const int v, const int f, const int c) {
++cnte; edge[cnte].to = v; edge[cnte].next = h[u]; edge[cnte].r = f; edge[cnte].c = c; h[u] = cnte;
++cnte; edge[cnte].to = u; edge[cnte].next = h[v]; edge[cnte].r = 0; edge[cnte].c = -c; h[v] = cnte;
}
queue<int> Q;
int dis[N], pre[N], a[N], ans = 0;
bool vis[N];
inline bool SPFA(){
while (!Q.empty()) Q.pop();
for (int i = S; i <= T; ++i) vis[i] = false, dis[i] = INF;
dis[S] = 0; Q.push(S); a[S] = INF; pre[S] = 0;
int now;
while (!Q.empty()) {
now = Q.front(); Q.pop();
vis[now] = false;
for (int i = h[now]; i; i = edge[i].next) {
if (edge[i].r && dis[edge[i].to] > dis[now] + edge[i].c) {
dis[edge[i].to] = dis[now] + edge[i].c;
pre[edge[i].to] = i;
a[edge[i].to] = min(a[now], edge[i].r);
if (!vis[edge[i].to]) {
Q.push(edge[i].to);
vis[edge[i].to] = true;
}
}
}
}
if (dis[T] == INF) return false;
ans += a[T] * dis[T];
for (now = T; now != S; now = edge[pre[now]^1].to) {
edge[pre[now]].r -= a[T];
edge[pre[now]^1].r += a[T];
}
return true;
}
inline int MCMF() {
ans = 0;
while (SPFA());
return ans;
}
inline int GET(int x) {
for (int i = h[x]; i; i = edge[i].next)
if (edge[i].r) return edge[i].to;
}
}
int A[105][105], rd[105], cnt[105], sum, ans, tot;
int main() {
n = getint();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
A[i][j] = getint();
if (A[i][j] == 1) ++rd[j];
if (A[i][j] == 2) {
++cnt[i];
++sum;
}
}
sum >>= 1;
S = 0; T = sum + n + 1;
for (int i = 1; i <= n; ++i) ans += rd[i] * rd[i];
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
if (A[i][j] == 2) {
MIC::ins(S, ++tot, 1, 0);
MIC::ins(tot, sum+i, 1, 0);
MIC::ins(tot, sum+j, 1, 0);
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= cnt[i]; ++j) {
MIC::ins(sum+i, T, 1, rd[i]*2+1);
++rd[i];
}
ans += MIC::MCMF();
ans -= (n - 1) * n / 2;
ans /= 2;
ans = n * (n-1) * (n-2) / 6 - ans;
printf("%d\n", ans);
tot = 0;
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (A[i][j] == 2) {
A[i][j] = (MIC::GET(++tot)-sum == i);
A[j][i] = !A[i][j];
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
printf("%d ", A[i][j]);
putchar('\n');
}
}
|