【hihocoder 1424】 Asa's Chess Problem（有源汇上下界网络流）

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define rep(i,l,r) for(int i=0,ed=r;i<ed;++i)
const int INF = 0x3f3f3f3f;
const int N = 200;
const int M = 100001;
using namespace std;

namespace MinCostMaxFlow {
	struct edge{int to,nxt,cap,flow,cost;}e[M];
	int head[N],cnt;
	int pre[N],dis[N];
	bool vis[N];
	void init(){
		cnt=0;mem(head,-1);
	}
	void addEdge(int u,int v,int w,int c=0){
		e[cnt]=(edge){v,head[u],w,0,c};head[u]=cnt++;
		e[cnt]=(edge){u,head[v],0,0,-c};head[v]=cnt++;
	}
	bool spfa(int s,int t,int n){
		queue<int>q;
		rep(i,0,n)dis[i]=INF,vis[i]=0,pre[i]=-1;
		dis[s]=0;vis[s]=1;q.push(s);
		while(!q.empty()){
			int u=q.front();q.pop();vis[u]=0;
			for(int i=head[u];~i;i=e[i].nxt){
				int v=e[i].to;
				if(e[i].cap>e[i].flow && dis[v]>dis[u]+e[i].cost){
					dis[v]=dis[u]+e[i].cost;pre[v]=i;
					if(!vis[v]){vis[v]=1;q.push(v);}
				}
			}
		}
		if(pre[t]==-1)return 0;
		return 1;
	}
	int solve(int s,int t,int n,int &cost){
		int flow=0;
		cost=0;
		while(spfa(s,t,n)){
			int Min=INF;
			for(int i=pre[t];~i;i=pre[e[i^1].to])
				if(Min>e[i].cap-e[i].flow)Min=e[i].cap-e[i].flow;
			for(int i=pre[t];~i;i=pre[e[i^1].to])
				e[i].flow+=Min,e[i^1].flow-=Min,cost+=e[i].cost*Min;
			flow+=Min;
		}
		return flow;
	}
}

int n;
int a[N][N];
int S=1,T=2,s=3,t=4;
int need;
int in[N];

void add(int u,int v,int w,int c=0){
	if(u==S)need+=w;
	if(!w)return;
	MinCostMaxFlow::addEdge(u,v,w,c);
}

void init(){
	MinCostMaxFlow::init();
	need=0;
	mem(in,0);
}

inline int rID(int row){
	return row+t+1;
}

inline int cID(int col){
	return col+t+1+n;
}

void build(int k){
	if(in[k]>0)add(S,k,in[k]);
	else add(k,T,-in[k]);
}

void solve(){
	int ans;
	int ok=need==MinCostMaxFlow::solve(S,T,cID(n-1)+1,ans);
	printf("%d\n",ok?ans:-1);
}

int main(){
	while(~scanf("%d",&n)){
		init();
		
		rep(i,0,n)rep(j,0,n){
			scanf("%d",&a[i][j]);
			if(a[i][j]){
				--in[rID(i)];
				++in[cID(j)];
			}
		}
		
		rep(i,0,n){
			int l,r;
			scanf("%d%d",&l,&r);
			add(s,rID(i),r-l);
			in[rID(i)]+=l;in[s]-=l;
		}
		
		rep(i,0,n){
			int l,r;
			scanf("%d%d",&l,&r);
			add(cID(i),t,r-l);
			in[cID(i)]-=l;in[t]+=l;
		}
		
		rep(i,0,n)
			rep(j,0,2)
				build(j?rID(i):cID(i));
		
		build(s);build(t);
		add(t,s,INF);
		
		rep(i,0,n*n/2){
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			--x1;--y1;--x2;--y2;
			if(a[x1][y1]^a[x2][y2]){
				if(x1==x2){
					if(a[x1][y1])swap(y1,y2);
					add(cID(y2),cID(y1),1,1);
				}
				else{
					if(a[x1][y1])swap(x1,x2);
					add(rID(x1),rID(x2),1,1);
				}
			}
		}
		
		solve();
	}
	return 0;
}