BZOJ 2597 WC2007 剪刀石頭布 費用流

題目大意：給定一個競賽圖，一些邊沒有指定方向，求一個指定方向的方案使競賽圖中三元環的數量最多

直接做不好做，我們考慮補集法

三個點之間如果不是三元環，那麼一定有一個點有兩條出邊

於是我們可以得到ans=C(n,3)-ΣC(degree[x],2)

於是我們考慮費用流的模型

每條邊化為一個點

從源點向每個點連n-1條邊，流量為1，費用為0,1,...,n-2

一條邊如果可以或必須成為一個點的出邊 那麼就從這個點出發向這條邊連一條流量為1，費用為零的邊

每條邊向匯點連一條流量為1，費用為零的邊

跑最小費用最大流即可

#include 
#include 
#include 
#include 
#define M 11000
#define S 0
#define T 10999
#define INF 0x3f3f3f3f
using namespace std;
struct abcd{
	int to,f,cost,next;
}table[1001001];
int head[M],tot=1;
int n,cnt,ans,map[110][110],edge[110][110];
void Add(int x,int y,int f,int cost)
{
	table[++tot].to=y;
	table[tot].f=f;
	table[tot].cost=cost;
	table[tot].next=head[x];
	head[x]=tot;
}
void Link(int x,int y,int f,int cost)
{
	Add(x,y,f,cost);
	Add(y,x,0,-cost);
}
bool Edmons_Karp()
{
	static int q[65540],f[M],from[M],cost[M];
	static unsigned short r,h;
	static bool v[M];
	int i;
	memset(cost,0x3f,sizeof cost);
	q[++r]=S;f[S]=INF;cost[S]=0;f[T]=0;
	while(r!=h)
	{
		int x=q[++h];v[x]=0;
		for(i=head[x];i;i=table[i].next)
			if( table[i].f && cost[x]+table[i].cost>n;cnt=n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&map[i][j]);
	for(i=1;i<=n;i++)
		for(j=0;j<=n-2;j++)
			Link(S,i,1,j);
	for(i=1;i<=n;i++)
		for(j=1;j