题目地址：洛谷：【P4249】[WC2007]剪刀石头布 – 洛谷、BZOJ：Problem 2597. — [Wc2007]剪刀石头布

题目描述

在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到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。

输出格式：
输出文件的第1行是一个整数，表示在你安排的比赛结果中，出现了多少剪刀石头布情况。
输出文件的第2行开始有一个和输入文件中格式相同的N行N列的数字矩阵。第(i+1)行第j个数字描述了i和j之间的比赛结果，1表示i赢了j，0表示i负于j，与输入矩阵不同的是，在这个矩阵中没有表示比赛尚未进行的数字2；对角线上的数字都是0。输出矩阵要保证合法，不能发生矛盾。

输入输出样例

输入样例#1：

3
0 1 2
0 0 2
2 2 0

输出样例#1：

1
0 1 0
0 0 1
1 0 0

说明

【评分标准】
对于每个测试点，仅当你的程序的输出第一行的数字和标准答案一致，且给出了一个与之一致的合法方案，你才能得到该测试点的满分，否则该测试点得0分。
【数据范围】
30%的数据中，N≤6；
100%的数据中，N≤100。

题解

考虑一下这样的三元组的相关性质，比如：1.这是个三元环，好像没用。2.三元组构成的子图中，所有点的入度/出度都是1，好像也没用。正难则反，我们考虑一下不符合条件的三元组，则子图中存在点的入度为2，也存在点的入度为0，出度也有类似性质。我们不妨考虑入度，假如点i的入度为d_i，则不合法的三元组个数是\sum_{i=1}^n \mathrm{C}_{d_i}^2，这是因为任意选择两个有出边连向i的点与i组成三元组都是不合法的，而且由于是有向图，这个统计并不会重复。现在我们有办法求出不合法的三元组个数了，用总三元组数减去它就是合法的三元组数了，即答案是
\mathrm{C}_n^3 - \sum_{i=1}^n \mathrm{C}_{d_i}^2
其中
\mathrm{C}_n^3 = \frac{n(n-1)(n-2)}{6}
我们考虑一条不确定的边对它所连接的两个点的入度造成的影响，以及对答案造成的影响。实际上一条不确定的边会导致它连接的两个点其中一个点的入度+1，而我们知道有
\mathrm{C}_n^2 - \mathrm{C}_{n-1}^2 = n-1
这就是一个费用递增的模型！我们可以建立源→不确定的边→原图中的点→汇的网络。其中源→不确定的边→原图中的点的所有边为容量1费用0的边，表示选择一种方案。而用原图中的点→汇的边来表示费用递增，即设置为容量1费用从确定的入度到入度上限的一系列边，每一条边表示入度+1对答案的贡献。在这个网络中跑最小费用最大流即可。
对于输出方案，我们检查不确定的边在网络中的对应点的出边，看流流向了哪边，就可以确定该边在方案中的方向。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int f[MAXN], dis[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(f, 0, sizeof(f));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inque[s] = true; f[s] = INF; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                pre[v] = u; pree[v] = i;
                f[v] = std::min(f[u], gra[i].cap);
                dis[v] = dis[u] + gra[i].cost;
                if(!inque[v]) {
                    inque[v] = true;
                    que.push(v);
                }
            }
        }
    }
    return f[t];
}

int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
        }
        flow += f[t];
        cost += f[t] * dis[t];
    }
}

int n, m, mmp[105][105], deg[105], S, T;

// 1 ~ n point
// n+1 ~ edge

int main() {
    memset(head, -1, sizeof(head));
    m = n = readint();
    S = n * n + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            mmp[i][j] = readint();
            if(mmp[i][j] == 2 && i < j) {
                addedge(S, ++m, 1, 0);
                addedge(m, i, 1, 0);
                addedge(m, j, 1, 0);
            } else if(mmp[i][j] == 1) {
                deg[j]++;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        cost += deg[i] * (deg[i] - 1) / 2;
        for(int j = deg[i]; j < n - 1; j++) {
            addedge(i, T, 1, j);
        }
    }
    mcmf(S, T);
    printf("%d\n", n * (n - 1) * (n - 2) / 6 - cost);
    m = n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(mmp[i][j] == 2) {
                int to;
                for(int k = head[++m]; ~k; k = gra[k].nxt) {
                    if(gra[k].cap == 0) {
                        to = gra[k].to;
                        break;
                    }
                }
                if(to == j) {
                    mmp[i][j] = 1; mmp[j][i] = 0;
                } else if(to == i) {
                    mmp[j][i] = 1; mmp[i][j] = 0;
                }

            }
            printf("%d ", mmp[i][j]);
        }
        puts("");
    }
    return 0;
}