# bzoj 2597 [Wc2007]剪刀石头布

3

0 1 2

0 0 2

2 2 0

1

0 1 0

0 0 1

1 0 0

100%的数据中，N≤ 100。

### 题解

C(w[i],2)累计到sum中(其中sum表示非石头剪刀布的数目)，从该选手节点向汇点连边，容量为1，费用依次为w[i]，w[i]+1，w[i]+2……连多少条边呢？n条一定够用了。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 20010
#define inf 0x33333333
using namespace std;
typedef pair<int, int> Pair;
struct MFMC {
struct node {
int from, to, next, flow, cost;
}e[N * 3];
int tot, st[N], pe[N], pv[N], dis[N], vis[N];
void init() {
tot = -1, memset(e, -1, sizeof e);
memset(st, -1, sizeof st);
}
void add(int x, int y, int z, int zz) {
e[++tot].to = y, e[tot].from = x;
e[tot].flow = z, e[tot].cost = zz;
e[tot].next = st[x], st[x] = tot;
}
void add_edge(int x, int y, int z, int zz) {
}
queue <int> que;
bool spfa(int S, int T) {
memset(dis, 0x33, sizeof dis);
memset(vis, 0, sizeof vis);
que.push(S), vis[S] = 1, dis[S] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
vis[now] = 0;
for (int i = st[now]; ~i; i = e[i].next)
if (e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost) {
dis[e[i].to] = dis[now] + e[i].cost;
pe[e[i].to] = i, pv[e[i].to] = now;
if (!vis[e[i].to])
vis[e[i].to] = 1, que.push(e[i].to);
}
}
return dis[T] < inf;
}
Pair mfmc(int S, int T) {
int COST = 0, FLOW = 0, flow;
while(spfa(S, T)) {
flow = inf;
for (int i = T; i != S; i = pv[i])
flow = min(flow, e[pe[i]].flow);
COST += flow * dis[T];
FLOW += flow;
for (int i = T; i != S; i = pv[i])
e[pe[i]].flow -= flow, e[pe[i] ^ 1].flow += flow;
}
return make_pair(FLOW, COST);
}
}mcmf;
int n, m, x, y, z, k, d[N], anss, a[110][110], w[N];
int main() {
mcmf.init();
scanf("%d", &n);
int S = n * (n + 1) + 1, T = S + 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
scanf("%d", &a[i][j]);
if (a[i][j] != 2)
w[i] += a[i][j];
}
for (int i = 1; i <= n; ++i) {
anss += (w[i] - 1) * w[i] / 2;
for (int j = 0; j < n; ++j)
mcmf.add_edge(n * n + i, T, 1, w[i] + j);
}
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j)
if (a[i][j] == 2) {
int now = (i - 1) * n + j;
mcmf.add_edge(now, n * n + i, 1, 0);
mcmf.add_edge(now, n * n + j, 1, 0);
}
Pair ans = mcmf.mfmc(S, T);
for (int i = 0; i <= mcmf.tot; ++i)
if (mcmf.e[i].from >= 1 && mcmf.e[i].from <= n * n &&
mcmf.e[i].to <= n * (n + 1) && !mcmf.e[i].flow) {
int now = mcmf.e[i].from,
x = (now - 1) / n + 1, y = now - (x - 1) * n;
if (mcmf.e[i].to == n * n + y) swap(x, y);
a[x][y] = 1, a[y][x] = 0;
}
int all = n * (n - 1) * (n - 2) / 6 - ans.second - anss;
printf("%d\n", all);
for (int i = 1; i <= n; ++i, puts(""))
for (int j = 1; j <= n; ++j)
printf("%d ", a[i][j]);
}