BZOJ 2597 WC 2007 가위바위보 비용 흐름

제목 의 대의: 경기 그림 을 정 하고 일부 변 에 방향 을 지정 하지 않 으 며 방향 을 지정 하 는 방안 을 구 해서 경기 그림 에서 3 원 링 의 수량 을 가장 많 게 한다.
직접 하기 가 쉽 지 않 으 니, 우 리 는 보 집 법 을 고려 합 시다.
세 점 사이 에 만약 삼원 환 이 아니라면, 반드시 한 점 은 두 개의 가장자리 가 있 을 것 이다.
그래서 우 리 는 ans = C (n, 3) -ΣC(degree[x],2)
그래서 우 리 는 비용 흐름 의 모델 을 고려 했다.
각 변 이 하나의 점 으로 변 하 다.
원점 에서 각 점 으로 n - 1 개의 변 을 연결 하고 유량 은 1 이 며 비용 은 0, 1,..., n - 2 이다.
한 변 이 가능 하거나 한 점 의 아웃 사 이 드 가 되 어야 한다 면 이 점 에서 출발 하여 이 변 으로 연 결 된 유량 은 1 이 고 비용 은 0 의 변 이다.
각 변 의 외환 점 에 연 결 된 유량 은 1 이 고 비용 은 0 의 변 이다.
최소 비용 으로 최대 흐름 을 달리 면 된다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#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<cost[table[i].to] )
			{
				cost[table[i].to]=cost[x]+table[i].cost;
				f[table[i].to]=min(f[x],table[i].f);
				from[table[i].to]=i;
				if(!v[table[i].to])
					v[table[i].to]=1,q[++r]=table[i].to;
			}
	}
	if(!f[T]) return false;
	ans-=cost[T]*f[T];
	for(i=from[T];i;i=from[table[i^1].to])
		table[i].f-=f[T],table[i^1].f+=f[T];
	return true;
}
int main()
{
	
	//freopen("hand.in","r",stdin);
	//freopen("hand.out","w",stdout);
	
	int i,j;
	cin>>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<i;j++)
		{
			Link(++cnt,T,1,0);
			if(map[i][j]==0||map[i][j]==2)
				Link(i,cnt,1,0),edge[j][i]=tot-1;
			if(map[i][j]==1||map[i][j]==2)
				Link(j,cnt,1,0),edge[i][j]=tot-1;
		}
	ans=n*(n-1)*(n-2)/6;
	while( Edmons_Karp() );
	cout<<ans<<endl;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(i==j) printf("0%c",j==n?'
':' ');
			else printf("%d%c",!edge[i][j]||table[edge[i][j]].f?0:1,j==n?'
':' ');
		}
	return 0;
}
/*
S 0
            1~n
            n+1~n+(n*(n-1)/2)
T 10999
S     n-1      1    0~n-2
        T      1    0
                  1    0
      
       
*/