題目暫無(wú)鏈接
( 北京2016區(qū)域賽C題 )

題目大意

給出一個(gè)N×N的01矩陣(N<=50，且N為偶數(shù))。有N*N/2對(duì)可交換格子，每個(gè)格子有且僅有一個(gè)可交換對(duì)象。并且，每對(duì)可交換的格子必然在同一行或同一列。每交換一次的代價(jià)是1。對(duì)于每一行和每一列，都有一個(gè)1的個(gè)數(shù)的上界和下界。
問(wèn)，最少執(zhí)行多少次交換操作，可以滿足所有行和列的1的個(gè)數(shù)的要求，

解答

比較明顯的網(wǎng)絡(luò)流構(gòu)圖，需要用到上下界，注意構(gòu)圖點(diǎn)數(shù)不要太多，否則會(huì)TLE，該壓縮的必須要壓縮。

把每一行每一列都看成一個(gè)狀態(tài)，由于可交換的格子必然在同一行或同一列，所以每次交換必然只是從一個(gè)狀態(tài)流向另一個(gè)狀態(tài)。所以，我們可以先預(yù)處理出開(kāi)始狀態(tài)每一行每一列有多少個(gè)1( 記為g[i] )，從源點(diǎn)S向狀態(tài)i (行或列)連一條上界下界均為g[i]，費(fèi)用為0的邊。每個(gè)狀態(tài)i都向匯點(diǎn)T連一條上下界為讀入要求，費(fèi)用為0的邊。然后，統(tǒng)計(jì)出N*N/2對(duì)交換格子交換后由狀態(tài)i 到狀態(tài) j的個(gè)數(shù)( 先用二維數(shù)組壓縮統(tǒng)計(jì),記為swg[i][ j ] )，狀態(tài)i向狀態(tài)j連一條下界為0，上界為swg[i][ j ]，費(fèi)用為1的邊。

根據(jù)上述的構(gòu)圖，新添超級(jí)源點(diǎn)SS和超級(jí)匯點(diǎn)ST，根據(jù)模型，轉(zhuǎn)化為下界均為0的網(wǎng)絡(luò)流。最后，直接求解費(fèi)用流即可。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>

#define bll long long
#define dou double
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define rep(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))
//__builtin_popcountll

using std::sort;
using std::max;
using std::min;
using std::abs;
using std::swap;

// 費(fèi)用流模板，封裝在namespace里，避免變量，函數(shù)沖突
namespace fyl
{
    const int maxnode=100+100,maxedge=100*100+100*4+10;
    const int oo=1<<30;
    struct Edge
    {
        int node,next,flow,cost;
        Edge(int a=0,int b=0,int c=0,int d=0)
        {
            node=a,next=b,flow=c,cost=d;
        }
    }E[maxedge*2];
    int cnt;                    // 邊數(shù)統(tǒng)計(jì)
    int head[maxnode],path[maxnode],pre[maxnode],F[maxnode];
    int o[200000];              // spfa隊(duì)列，開(kāi)的較大，如果不夠可改成循環(huán)隊(duì)列
    bool vis[maxnode];          // spfa判斷是否點(diǎn)在隊(duì)列里

    void init()                 // 初始化，多組數(shù)據(jù)必須調(diào)用
    {
        cnt=0;
        memset(head,255,sizeof head);
    }
    void add_edge(int x,int y,int f,int c)  // 建邊，使用頻率很高，可以考慮using
    {
        E[cnt]=Edge(y,head[x],f,c),head[x]=cnt++;
        E[cnt]=Edge(x,head[y],0,-c),head[y]=cnt++;
    }
    bool spfa(int S,int T,int N)            // 找一條從S到T的最小費(fèi)用路徑，N是網(wǎng)絡(luò)流結(jié)點(diǎn)最后一個(gè)編號(hào)
    {
        for (int i=0; i<=N; i++) F[i]=oo;
        int h=0,t=0;
        o[t]=S; F[S]=0; vis[S]=1;
        for (; h<=t; h++)
        {
            int x=o[h];
            for (int i=head[x]; i!=-1; i=E[i].next)
            {
                int y=E[i].node;
                if (E[i].flow>0 && F[x]+E[i].cost<F[y])
                {
                    F[y]=F[x]+E[i].cost;
                    pre[y]=x;
                    path[y]=i;
                    if (!vis[y]) vis[o[++t]=y]=1;
                }
            }
            vis[x]=0;
        }
        return F[T]!=oo;
    }
    void get_ans(int S,int T,int &flow,int &cost)   // 找到路徑后，得到流量和費(fèi)用
    {
        int minf=oo;
        for (int x=T; x!=S; x=pre[x])
            minf=min(minf,E[path[x]].flow);
        for (int x=T; x!=S; x=pre[x])
        {
            E[path[x]].flow-=minf;
            E[path[x]^1].flow+=minf;
            cost+=E[path[x]].cost*minf;
        }
        flow+=minf;
    }
    void solve(int S,int T,int N,int &flow,int &cost)   // 建圖后求最小費(fèi)用最大流
    {
        while(spfa(S,T,N))
            get_ans(S,T,flow,cost);
    }
}

const int maxn=100+10;
int N;
int A[maxn][maxn],u[maxn],d[maxn];
int g[maxn],swg[maxn][maxn];

int Done()
{
    int S=0,T=2*N+1,num=2*N+1;  // 2*N個(gè)狀態(tài)，表示行和列，num表示點(diǎn)的編號(hào)
    int SS=++num,ST=++num;
    int sumdown=0;              // 下屆的和
    fyl::init();                // 初始化
    Mem(g,0);                   // 統(tǒng)計(jì)初始矩陣每個(gè)狀態(tài)的1的個(gè)數(shù)
    Mem(swg,0);                 // 統(tǒng)計(jì)狀態(tài)間的交換次數(shù)，用于壓縮邊
    For(i,1,N)
        For(j,1,N)
        {
            scanf("%d",&A[i][j]);
            g[i]+=A[i][j];
            g[j+N]+=A[i][j];
        }
    For(i,1,2*N) scanf("%d%d",&d[i],&u[i]); // 讀入行列上下界
    For(i,1,N*N/2)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if (A[x1][y1]!=A[x2][y2])
        {
            if (A[x1][y1]==0) swap(x1,x2),swap(y1,y2);
            if (x1==x2) 
                swg[y1+N][y2+N]++;
            else
                swg[x1][x2]++;
        }
    }
    using fyl::add_edge;                // 頻繁出現(xiàn)，先using
    For(i,1,2*N)
    {
        if (g[i])
        {
            add_edge(SS,i,g[i],0);
            add_edge(S,ST,g[i],0);
            sumdown+=g[i];
        }
        if (d[i]>0)
        {
            add_edge(SS,T,d[i],0);
            add_edge(i,ST,d[i],0);
            u[i]-=d[i];
            sumdown+=d[i];
        }
        if (u[i]) add_edge(i,T,u[i],0);
    }
    For(i,1,2*N)
        For(j,1,2*N)
            if (swg[i][j]) add_edge(i,j,swg[i][j],1);
    add_edge(T,S,fyl::oo,0);
    int flow=0,cost=0;
    fyl::solve(SS,ST,num,flow,cost);
    if (flow!=sumdown) return -1;   // 最大流要等于下屆可，否則無(wú)解
    return cost;                    // 返回有解的情況下的最小費(fèi)用
}


int main(int argc, char* argv[])
{
    for (; scanf("%d",&N)!=EOF; )
    {
        int ans=Done();
        printf("%d\n",ans);
    }
    return 0;
}