UVALive-7670
ICPC北京2016-C题 hihocoder 1424
题意
有个 \(N\times N\) 的棋盘，告诉你每个格子黑色(1)或白色(0)，以及每对能相互交换的同行或同列格子，每个格子只在一对中，即共有\(N\times N /2\)对。求最少交换次数使得每行每列的黑格子总数满足给出的上下范围：若最终第i行,第j列分别有\(R[i],C[j]\)个黑格子，那么需要让\(Rl[i]\le R[i]\le Rh[i],Cl[j]\le C[i]\le Ch[j]\)。
如果不存在方案输出-1。
\(T\le 100,2\le N \le 50\)。
题解
判定给定行和列和的01矩阵的存在性可以用网络流来做，所以这题也可以联想到用网络流求解。
建图，建边费用默认0：
- 每一行为一个点，编号rID(i)
- 每一列为一个点，编号cID(i)
- 源点为s，汇点为t
- 第i行第j列为1，则连边rID(i)->cID(j)，上下界都是1
- 连边s->rID(i)，上下界就是该行的限制
- 连边cID(i)->t，上下界就是该列的限制
- (x1,y1)和(x2,y2)可以交换
- 如果是同色，没有意义，不用管；
- 如果不同色，假设(x1,y1)是1：
- 若同行：连边cID(y1)->cID(y2)，上界1，下界0，费用1。
- 若同列：连边rID(x2)->rID(x1)，上界1，下界0，费用1。
那么如果s到t存在可行流，就代表有解。最大流的最小费用就是最少交换次数。
现在有一个有源汇的带上下界的网络流，我们知道怎么求解无源汇的带上下界的网络流，怎么转化呢？先将有源汇变成无源汇循环流：连边t->s，上界INF，下界0。接着就是将无源汇的带上下界的网络流变成没有下界（其实是下界为0）的网络流：
- 添加超级源点S，超级汇点T
- 原图每条边容量=原来的上界-下界
- 原图每个点u，\(in\) 为流入的流量下界和，\(out\) 为流出的流量下界和
- \(in>out\)，则连S->u，容量in-out
- \(in<out\)，则连u->T，容量out-in
S到T跑最大流，如果最大流等于S的出边流量之和，那么就有解。因为要求最小费用，所以跑最小费用最大流。
另外看到的建图是：
- s->rID(i)或s->cID(i)，上下界是初始的行和或列和
- rID(i)->t或sID(i)->t，上下界是给定的行和或列和的限制
- (x1,y1)和(x2,y2)可以交换，不同的地方就是同列时：连边rID(x1)->rID(x2)。
后面解法就相同了。。。
代码
#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;
}