题解 P4249 【[WC2007]剪刀石头布】

[$\Large\color{#FFBBFF}\textit{Tian-Xing's blog}$](https://Tian-Xing.github.io) ------------ # Description [传送门](https://www.luogu.com.cn/problem/P4249) ------------ # Solution 首先发现直接求这种三元组不打好求，那么考虑球不满足这种关系的三元组的数量。 注意到一个三元组，如果不满足这种关系，肯定分别赢了$0$，$1$，$2$场。 那么我们如果知道了每个人赢的场数$y_i$，不具有这种关系的三元组数量就是$\sum \frac{y_i \times (y_i - 1}{2}$。 因为要使满足这种关系的三元组数量最多，所以我们建立的合法方案要使$\sum \frac{y_i \times (y_i - 1}{2}$最小。考虑用网络流来求解。 首先要满足是一种合法方案，可以这样建模，首先每个人向$T$连一条容量为$n$的有向边，然后对于一个还没有发生的比赛，新建一个节点$tmp$，从$tmp$分别向$i$和$j$连一条容量为$1$的有向边，从$S$向$tmp$链接一条容量为$1$的有向边。这样建模跑出来的最大流就是一种合法方案。 现在考虑如何在跑最大流的时候使$\sum \frac{y_i \times (y_i - 1)}{2}$最小，将每个人向$T$连的有向边拆成容量为$1$的若干条有向边，费用分别为$0$，$1$，$2 \dots$这样连边是因为如果一个人的胜利场数增加一，$\frac{y_i \times (y_i - 1}{2}$的变化会呈现一种等差数列的形式，而这样将边拆开，每次只会增广费用最小的一条路，所以能保证正确性。 需要注意的是，如果一个人本来有一些胜利场数，要在原先的胜利场次基础上进行拆边和建模。 ------------ # Code ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; #define int long long const int INF = 999999999; const int N = 1000050; const int M = 2000050; int n, s, t, head[N], cur[N], d[N], vis[N], a[500][500], num = 1, cnt, y[N], ans, maxflow, mincost, neww[N][3], diao; struct Node { int next, to, flow, dis; } edge[M * 2]; void Addedge(int u, int v, int w, int c) { edge[++num] = (Node){ head[u], v, w, c}; head[u] = num; } void Add(int u, int v, int w, int c) { Addedge(u, v, w, c); Addedge(v, u, 0, -c); return; } template <class T> void Read(T &x) { x = 0; int p = 0; char st = getchar(); while (st < '0' || st > '9') p = (st == '-'), st = getchar(); while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar(); x = p ? -x : x; return; } template <class T> void Put(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) Put(x / 10); putchar(x % 10 + '0'); return; } void Work(int x) { for (int i = y[x] + 1; i <= n; i++) { Add(x, t, 1, i - 1); } return; } int Bfs() { queue<int> q; for (int i = 0; i <= cnt; i++) d[i] = INF, vis[i] = 0; d[s] = 0; vis[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; i; i = edge[i].next) if (edge[i].flow > 0 && d[edge[i].to] > d[u] + edge[i].dis) { d[edge[i].to] = d[u] + edge[i].dis; if (!vis[edge[i].to]) { vis[edge[i].to] = 1; q.push(edge[i].to); } } } return d[t] != INF; } int Dinic(int x, int flow) { if (x == t || !flow) return flow; int rest = flow, k; vis[x] = 1; for (int i = cur[x]; i && rest; i = edge[i].next) { int v = edge[i].to; cur[x] = i; if (!vis[edge[i].to] && edge[i].flow > 0 && d[edge[i].to] == d[x] + edge[i].dis) { int v = edge[i].to; int k = Dinic(v, min(rest, edge[i].flow)); // if (!k) dis[edge[i].to] = INF; rest -= k; edge[i].flow -= k; edge[i ^ 1].flow += k; mincost += k * edge[i].dis; } } vis[x] = 0; return flow - rest; } void Solve() { while(Bfs()) { for (int i = 0; i <= cnt; i++) cur[i] = head[i]; maxflow += Dinic(s, INF); } return; } signed main() { Read(n); cnt = n + 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { Read(a[i][j]); if (a[i][j] == 1) y[i]++; } s = 0; t = n + 1; for (int i = 1; i <= n; i++) ans += y[i] * (y[i] - 1) / 2, Work(i); for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) if (a[i][j] == 2) { int tmp = ++cnt; neww[++diao][1] = i; neww[diao][2] = j; Add(s, tmp, 1, 0); Add(tmp, j, 1, 0); Add(tmp, i, 1, 0); neww[diao][0] = num; } Solve(); ans += mincost; Put(n * (n - 1) * (n - 2) / 6 - ans); putchar('\n'); for (int i = 1; i <= diao; i++) a[neww[i][1]][neww[i][2]] = edge[neww[i][0]].flow > 0 ? 1 : 0, a[neww[i][2]][neww[i][1]] = a[neww[i][1]][neww[i][2]] ^ 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) Put(a[i][j]), putchar(' '); putchar('\n'); } return 0; } ```