VJ193259 C Asa's Chess Problem

Concept

上下界网络流

顾名思义，比普通的网络流多出了下界。
考虑将下界的流量限制进行转化。将原来的边(e, v1->v2)拆边，拆出一条上界为 max-min 的边(e1)，和一条上界为 min 的边(e2, 虚拟存在)。 e2 需要满足满流方才有解，但满流的同时还需要保证流量守恒（入流==出流）。故而构造虚拟源点 SS 和虚拟汇点 TT .

对于点v, 若：
下限入流等于下限出流，则两者平衡，可以认为这两个流出流入的流量都不存在。
下限入流(flowin)大于下限出流(flowout)，则 SS 向 v 连一条容量为 flowin-flowout 的边，弥补不足流量。
下限入流(flowin)小于下限出流(flowout)，则 v 向 TT 连一条容量为 flowout-flowin 的边，弥补过剩流量。

当且仅当 SS 的所有边都满流时有解。跑一遍 SS 到 TT 的最大流，然后验证即可。

有源汇上下界可行流

对于有源汇网络流，跑 SS 到 TT 的最大流的时候，要从原汇点 T 连一条容量为 INF 的边到原源点 S。因为 S 和 T 的流量不守恒，增加 T 到 S 的边可以解决这个问题。 T 到 S 的流量就是可行流的流量。

有源汇上下界最大流

先刷出可行流，验证是否存在 SS 到 TT 满流的可行解。
接下来刷 S 到 T 的最大流即可。无论再怎么刷 S 到 T 的最大流，都不会影响 SS 的出流，所以不会改变可行性。

Problem

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

Sample Input

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

Sample Output

2
4

Solution

以行和列建节点。从源点 S 向 行和列节点 连 容量上下界 为 当前对于行列的黑色棋子数目 的边。从汇点 行和列节点 向 T 连 容量上下界 为 给定黑色棋子范围 的边。对于配对的棋子，从 有黑色棋子的行或列 向 无黑色棋子的行或列 连 容量为1 的边。
用上下界网络流重构该图。跑 SS 到 TT 的最小费用最大流，判断是否可行解即可。不需要另外跑 S 到 T 的最大流。因为该题实际上求的是最小费用可行流，而不需要最大流。

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;
}