VJ193259 C Asa's Chess Problem

# VJ193259 C Asa's Chess Problem

Donny
October 29, 2017
2192
-

Tags in blue are handcrafted tags; Tags in green are generated using AutoTag.

## Problem

N X N 的棋盘和棋子。棋子有白有黑。同行或同列的某两个棋子是一对。要求通过交换配对的棋子，使得行和列的黑色棋子数在给定的范围。

2
0 0
1 1
2 2
0 1
0 2
0 2
1 1 2 1
1 2 2 2
4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
2 2
1 3
1 3
2 2
0 1
3 4
0 1
3 4
1 1 1 3
1 2 1 4
2 1 2 3
2 2 2 4
3 1 3 4
3 2 3 3
4 1 4 4
4 2 4 3

2
4

## Code

``````#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>

#define memz(_a) memset(_a,0,sizeof _a)

const int INF=0x7FFFFFFF;

const int maxn=55*2;
const int maxm=2*maxn*maxn;
struct EDG
{
int u,v,cap,f,c;
} es[maxm];
int fst[maxn],nxt[maxm];
int coe;
int V;

int D[maxn];
int SS,TT;

inline void init() {
coe=1; memz(fst); V=0;
memz(D);
}
inline void mkedg(int u,int v,int cap,int c)
{
es[++coe]={u,v,cap,0,c};
nxt[coe]=fst[u];
fst[u]=coe;
}

inline void mkedgulb(int u,int v,int cl,int cu,int cost)
{
D[u]-=cl; D[v]+=cl;
if (cu-cl==0) return;
mkedg(u,v,cu-cl,cost),mkedg(v,u,0,-cost);
}
inline void refactor()
{
SS=V+1; TT=V+2;
for (int v=1;v<=V;++v)
{
if (D[v]<0) mkedg(v,TT,-D[v],0),mkedg(TT,v,0,0);
if (D[v]>0) mkedg(SS,v,D[v],0),mkedg(v,SS,0,0);
}
}

int d[maxn];
int p[maxn];
int a[maxn];
bool inq[maxn];
bool spfa()
{
std::fill(d,d+maxn,INF);
memz(inq);

std::queue<int> Q;
d[SS]=0; p[SS]=0; a[SS]=INF;
Q.push(SS); inq[SS]=1;
while (!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=0;
for (int k=fst[u];k;k=nxt[k])
{
EDG& e=es[k];
if (e.cap>e.f && d[e.v]>d[u]+e.c)
{
d[e.v]=d[u]+e.c;
p[e.v]=k;
a[e.v]=std::min(a[u],e.cap-e.f);
if (!inq[e.v]) {
Q.push(e.v); inq[e.v]=1;
}
}
}
}
return d[TT]!=INF;
}
int mincost()
{
int flow=0,cost=0;
while (spfa())
{
flow+=a[TT];
cost+=d[TT]*a[TT];
for (int u=TT;u!=SS;u=es[p[u]].u) {
es[p[u]].f+=a[TT];
es[p[u]^1].f-=a[TT];
}
}
return cost;
}
bool checkulb()
{
for (int k=fst[SS];k;k=nxt[k])
{
if (es[k].f!=es[k].cap) return false;
}
return true;
}

int N;
int rowc[maxn],colc[maxn];
int G[maxn][maxn];
int r[maxn],c[maxn];
int S,T;

int main()
{
int x;
while (~scanf("%d",&N))
{
init();
memz(rowc); memz(colc);
S=++V; T=++V;
// S: 1; T: 2; rows: 3~N+2; cols:N+3~2N+2
for (int i=1;i<=N;++i)
for (int j=1;j<=N;++j)
{
scanf("%d",&G[i][j]);
if (G[i][j]) ++rowc[i],++colc[j];
}
int lc,uc;
for (int i=1;i<=N;++i)
{
scanf("%d%d",&lc,&uc);
r[i]=++V;
mkedgulb(S,r[i],rowc[i],rowc[i],0);
mkedgulb(r[i],T,lc,uc,0);
}
for (int j=1;j<=N;++j)
{
scanf("%d%d",&lc,&uc);
c[j]=++V;
mkedgulb(S,c[j],colc[j],colc[j],0);
mkedgulb(c[j],T,lc,uc,0);
}
int x1,x2,y1,y2;
for (int i=1;i<=N*N/2;++i)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if (G[x1][y1]==G[x2][y2]) continue;
if (!G[x1][y1]) std::swap(x1,x2),std::swap(y1,y2);
if (y1==y2) mkedgulb(r[x1],r[x2],0,1,1);
if (x1==x2) mkedgulb(c[y1],c[y2],0,1,1);
}
mkedg(T,S,INF,0); mkedg(S,T,0,0);
refactor();
int ans=mincost();
if (!checkulb()) ans=-1;
printf("%d\n",ans);
}

return 0;
}
``````