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

· · 题解

\Large\color{#FFBBFF}\textit{Tian-Xing's blog}

Description

传送门

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

#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;
}