「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$个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。

---

题目分析

最大化三元环的数目不好处理，补集转化为求最小的非三元环数目$num$。
$ans=C_n^3-num$。
考虑，一个非三元环一定有一个点的度数为$2$。
故用这一性质建模。
源点到原图的每个点连$n-1$条边，容量为$1$，费用为$0,1,2,\ldots,n-2$，表示每次破坏的三元环数目。
图中的每一条边（化边为点）若能够成为图中一个点的出边，则从该点向这条边连边，容量为$1$，费用为$0$。
原图的每一条边向汇点连一条容量为$1$，费用为$0$的边，表示每条边只能有一个方向。

跑费用流即可得出答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=6005;

struct Edge {
	int from,to,cap,flow,cost;
	Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

struct zkw_CostFlow {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool inque[maxn],vst[maxn];
	int a[maxn],dist[maxn],path[maxn];
	int flow,cost;
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	int AddEdge(int x,int y,int v,int f) {
		edges.push_back(Edge(x,y,v,0,f));
		edges.push_back(Edge(y,x,0,0,-f));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
		return m-2;
	}
	bool spfa() {
		for(int i=1; i<=n; i++)dist[i]=INT_MAX;
		memset(inque,0,sizeof(inque));
		dist[t]=0;
		inque[t]=1;
		deque<int>Q;
		Q.push_back(t);
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop_front();
			inque[Now]=0;
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(dist[Next]>dist[Now]+e.cost&&e.cap>e.flow) {
					dist[Next]=dist[Now]+e.cost;
					if(!inque[Next]) {
						inque[Next]=1;
						if(!Q.empty()&&dist[Next]<dist[Q.front()])Q.push_front(Next);
						else Q.push_back(Next);
					}
				}
			}
		}
		return dist[s]<INT_MAX;
	}
	int dfs(int Now,int a) {
		if(vst[Now])return 0;
		if(Now==t||a==0)return a;
		int flow=0;
		vst[Now]=1;
		for(int id:G[Now]) {
			Edge& e=edges[id];
			int Next=e.to;
			if(dist[Now]-e.cost!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				cost+=nextflow*e.cost;
				e.flow+=nextflow;
				edges[id^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		flow=cost=0;
		while(spfa()) {
			memset(vst,0,sizeof(vst));
			flow+=dfs(s,INT_MAX);
		}
		return flow;
	}
} zkw;

int n,a[105][105],link[105][105],cnt=0;

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			a[i][j]=Get_Int();
	zkw.init(n+(n-1)*n/2+2);
	int S=n+(n-1)*n/2+1,T=n+(n-1)*n/2+2,cnt=n;
	for(int i=1; i<=n; i++)
		for(int j=0; j<=n-2; j++)
			zkw.AddEdge(S,i,1,j);
	for(int i=1; i<=n; i++)
		for(int j=1; j<i; j++) {
			zkw.AddEdge(++cnt,T,1,0);
			if(a[i][j]==0||a[i][j]==2)link[j][i]=zkw.AddEdge(i,cnt,1,0);
			if(a[i][j]==1||a[i][j]==2)link[i][j]=zkw.AddEdge(j,cnt,1,0);
		}
	zkw.maxflow(S,T);
	printf("%d\n",n*(n-1)*(n-2)/6-zkw.cost);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			if(a[i][j]==2)printf("%d ",zkw.edges[link[i][j]].flow?1:0);
			else putchar(a[i][j]+'0'),putchar(' ');
		putchar('\n');
	}
	return 0;
}