省选专练 WC2007剪刀石头布

特殊的类最大权闭合图问题

列出方程求解

注意一个拆平方

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int INF=1e9+7;
const int N=1e6+100;
struct Front_star{
	int u,v,w,c,nxt;
}e[N*4];
int cnt=1;
int first[N]={0};
void addedge(int u,int v,int w,int c){
	cnt++;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].c=c;
	e[cnt].nxt=first[u];
	first[u]=cnt;
} 
void add(int u,int v,int w,int c){
	addedge(u,v,w,c);
	addedge(v,u,0,-c);
}
int g[101][101]={0};
int a[101][101]={0};
int n,S=0,T=3e4+100;
int w[N]={0};
int ans=0;
//
int dis[N*4]={0};
int pre[N*4]={0};
queue<int> q;
int inqueue[N*4]={0};
int SPFA(){
	for(int i=0;i<=T;i++)
		dis[i]=INF;
	memset(pre,0,sizeof(pre));
	q.push(S);
	dis[S]=0;
	while(!q.empty()){
		int   x=q.front();
		q.pop();
//		cout<<x<<" "<<'\n';
		inqueue[x]=0;
		for(int   i=first[x];i;i=e[i].nxt){
			int v=e[i].v;
			if(e[i].w&&e[i].c+dis[x]<dis[v]){
				dis[v]=dis[x]+e[i].c;
				pre[v]=i;
				if(!inqueue[v]){
					inqueue[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dis[T]!=INF;
}
int MCMF(){
	int ans=0;
	while(SPFA()){
//		cout<<"-----"<<endl;
		int s=INF;
		for(int i=pre[T];i;i=pre[e[i^1].v])
			s=min(s,e[i].w);
		for(int i=pre[T];i;i=pre[e[i^1].v]){
			e[i].w-=s;
			e[i^1].w+=s;
		}
		ans+=dis[T]*s;
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	S=n*n+1+n;
	T=S+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&g[i][j]);
			if(g[i][j]!=2){
				w[i]+=g[i][j];
			}
		} 
	}
	for(int i=1;i<=n;i++)  {  
        ans+=(w[i]-1)*w[i]/2;  
        int tmp=n*n+i;  
        for(int j=0;j<=n-1;j++) 
			add(tmp,T,1,w[i]+j);  
    }  
    for(int i=1;i<=n-1;i++) 
		for(int j=i+1;j<=n;j++) 
			if(g[i][j]==2){  
        		int tmp=(i-1)*n+j;  
        		add(S,tmp,1,0);  
        		add(tmp,n*n+i,1,0);  
        		add(tmp,n*n+j,1,0);  
    		} 
	/*
	for(int i=1;i<=n;i++){
		ans+=w[i]*(w[i]-1)/2;
		for(int j=0;j<=n-1;j++){
			add(n*n+i,T,1,w[i]+j);//本质是拆平方 
		}
	}
	for(int i=0;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i][j]==2){
				add(S,(i-1)*n+j,1,0);
				add((i-1)*n+j,n*n+j,1,0);
				add((i-1)*n+j,n*n+i,1,0);
			}
		}
	}*/
	ans+=MCMF();
	for(int i=2;i<=cnt;i++){
//		cout<<e[i].u<<" "<<e[i].v<<'\n';
		if(e[i].u>1&&e[i].u<=n*n&&e[i].v<=(n+1)*n&&!e[i].w){
			int u=e[i].u;
			int x=(u-1)/n+1;
			int y=u-(x-1)*n;
//			cout<<x<<" "<<y<<"_x _y"<<'\n';
			if(e[i].v==n*n+y){
				swap(x,y);	
			}
			a[x][y]=1;
			a[y][x]=0;
		}
	}    
	for(int i=2;i<=cnt;i++) 
		if (e[i].u>=1&&e[i].u<=n*n&&e[i].v<=n*(n+1)&&!e[i].w)  {  
        int tmp=e[i].u;  
        int x=(tmp-1)/n+1,y=tmp-(x-1)*n;  
        if (e[i].v==n*n+y) 
			swap(x,y);  
        a[x][y]=1;a[y][x]=0;  
    }  
	cout<<n*(n-1)*(n-2)/6-ans<<'\n';
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<'\n';
	}
	cout<<'\n';
}