bzoj 2597 [Wc2007]剪刀石头布
内容
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个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。
Input
输入文件的第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。输出矩阵要保证合法，不能发生矛盾。
Sample Input
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。
题解
转载:
是不是感觉这样一个问题很难和费用流扯上关系？但它实际上是有关系的…
首先我们可以转化为补集问题，也就是非石头剪刀布的情况。如果三个人之间的关系不是石头剪刀布，那么一定有某个人赢了另外两个人(这是很容易证明的)。假设第i个人赢了w[i]局，那么非石头剪刀布情况的总数为∑(C(w[i],2))，我们现在的任务就是让∑(C(w[i],2))最小(补集思想)。
下面我们就要考虑如何用费用流实现这个问题了。对于每一场比赛只有一个人可以获胜，我们很容易想到从源点到比赛节点连边，容量为1，费用为0；从比赛节点到两个选手节点连边，容量为1，费用为0。但是从选手向汇点怎么连边呢？这里的费用和流量成二次关系，我们可以用拆边法。拆边法顾名思义，就是把一条边拆成很多条边，但是整体的效果是没有改变的。
那怎么拆边呢？我们可以发现C(w[i],2)=w[i]*(w[i]-1)/2=1+2+3+…+(w[i]-1)。对于每个选手节点i，假设当前已经赢了w[i]场，我们就先将
C(w[i],2)累计到sum中(其中sum表示非石头剪刀布的数目)，从该选手节点向汇点连边，容量为1，费用依次为w[i]，w[i]+1，w[i]+2……连多少条边呢？n条一定够用了。
然后求最小费用最大流就可以了。
最终答案为C(n,3)-sum。
#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) {
add(x, y, z, zz), add(y, x, 0, -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(S, now, 1, 0);
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]);
}