题意：给你一个n*n(n<=50)的棋盘，棋盘上每个点0表示白棋，1表示黑棋。
接下来n行，第i行给出棋盘的 第i行 的黑棋数目的理想范围[x,y]。
接下来再n行，第i行给出棋盘的 第i列 的黑棋数目的理想范围[x,y]。
接下来n*n/2行，每行四个数，x1,y1,x2,y2，表示位置(x1,y1)的棋子可以和位置(x2,y2)的棋子相互交换位置。
保证每个棋子只会输入一次（可以且只可以交换一次），每两个可交换的棋子都在同一行或者同一列。
求最少交换次数，使每行每列的黑棋数目都在理想范围内。
如果无解，输出-1。
思路：
比赛的时候建图对了。。。可惜没带模板。。。最后一小时浪费了。。。（那这道题就是板子了）
其实还是很好想的，有源汇有上下界的最小费用最大流。
1、新建源点s，汇点t，统计黑棋总数目以及每一列、每一行黑棋的数目
2、源点s向每行、每列连边，容量为那一行、那一列的黑棋数目，费用为0
3、每一行、每一列向汇点t建边，容量上下界为理想数目上下界x、y，费用为0
4、对于同一行可交换的棋子，颜色相同忽略，颜色不同黑棋的那一行向白棋的那一行建边，容量为1，费用为1。
5、对于同一列同上建边。
然后套个有源汇有上下界的最小费用最大流板子就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=50+10;
int n;
int chs[maxn][maxn],rl[maxn],cl[maxn],rh[maxn],ch[maxn];
int r[maxn],c[maxn];
int s,t;
int sups,supt,digflow;
const int maxv=100+10;//最大顶点数
const int inf=2e9;//应大于费用总和
typedef pair<int,int> P;
struct Edge{int to,cap,rev,cost;}e;
vector<Edge>g[maxv];//图的邻接表示
int h[maxv],dist[maxv];//顶点的势、最短距离，若cost为整数，则为int
int prevv[maxv],preve[maxv],V;//最短路中的前驱节点、对应的边、顶点数
void addedge(int from,int to,int cap,int cost) // 加边
{
e.to=to;e.cap=cap;e.rev=g[to].size();e.cost=cost;
g[from].push_back(e);
e.to=from;e.cap=0;e.rev=g[from].size()-1;e.cost=-cost;
g[to].push_back(e);
}
void addedge(int from,int to,int low,int up,int cost)
{
digflow+=low;
addedge(sups,to,low,cost);
addedge(from,supt,low,cost);
addedge(from,to,up-low,cost);
}
int mincostflow(int s,int t,int f)//求解s~t,流量为f的最小费用
{
int res=0;
memset(h,0,sizeof(4*t+4));
while(f>0)
{
priority_queue<P, vector<P>, greater<P> > que;
fill(dist,dist+V,inf);
dist[s]=0;
que.push(P(0,s));
while(!que.empty())
{
P p=que.top();que.pop();
int v=p.second;
if(dist[v]<p.first) continue;
for(int i=0;i<g[v].size();i++)
{
Edge &E = g[v][i];
if(E.cap>0&&dist[E.to]>dist[v]+E.cost+h[v]-h[E.to])
{
dist[E.to]=dist[v]+E.cost+h[v]-h[E.to];
prevv[E.to]=v;
preve[E.to]=i;
que.push(P(dist[E.to],E.to));
}
}
}
if(dist[t]==inf) return -1;
for(int v=0;v<V;v++) h[v]+=dist[v];
//沿s到t的最短路尽量增广
int d=f;
for(int v=t;v!=s;v=prevv[v])
d=min(d,g[prevv[v]][preve[v]].cap);
f-=d;
res+=h[t]*d;
for(int v=t;v!=s;v=prevv[v])
{
Edge &E = g[prevv[v]][preve[v]];
E.cap-=d;
g[v][E.rev].cap+=d;
}
}
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
digflow=0;
s=2*n+1;sups=0;
t=2*n+2;supt=t+1;
memset(c,0,sizeof(c));
memset(h,0,sizeof(h));
for(int i=0;i<=supt;i++)
g[i].clear();
int mx=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&chs[i][j]);
c[j]+=chs[i][j];
h[i]+=chs[i][j];
mx+=chs[i][j];
}
for(int i=1;i<=n;i++)
{
addedge(s,i,h[i],h[i],0);
addedge(s,i+n,c[i],c[i],0);
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&rl[i],&rh[i]);
addedge(i,t,rl[i],rh[i],0);
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&cl[i],&ch[i]);
addedge(i+n,t,cl[i],ch[i],0);
}
for(int i=1,x1,x2,y1,y2;i<=(n*n)/2;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(chs[x1][y1]==chs[x2][y2]) continue;
if(chs[x1][y1]==0) swap(x1,x2),swap(y1,y2);
if(x1==x2) addedge(n+y1,n+y2,1,1);
else addedge(x1,x2,1,1);
}
addedge(t,s,mx,inf,0);
V=2*n+4;
int ans=mincostflow(sups,supt,digflow);
printf("%d\n",ans);
}
return 0;
}