题目暂无链接
( 北京2016区域赛C题 )
题目大意
给出一个N×N的01矩阵(N<=50，且N为偶数)。有N*N/2对可交换格子，每个格子有且仅有一个可交换对象。并且，每对可交换的格子必然在同一行或同一列。每交换一次的代价是1。对于每一行和每一列，都有一个1的个数的上界和下界。
问，最少执行多少次交换操作，可以满足所有行和列的1的个数的要求，
解答
比较明显的网络流构图，需要用到上下界，注意构图点数不要太多，否则会TLE，该压缩的必须要压缩。
把每一行每一列都看成一个状态，由于可交换的格子必然在同一行或同一列，所以每次交换必然只是从一个状态流向另一个状态。所以，我们可以先预处理出开始状态每一行每一列有多少个1( 记为g[i] )，从源点S向状态i (行或列)连一条上界下界均为g[i]，费用为0的边。每个状态i都向汇点T连一条上下界为读入要求，费用为0的边。然后，统计出N*N/2对交换格子交换后由状态i 到状态 j的个数( 先用二维数组压缩统计,记为swg[i][ j ] )，状态i向状态j连一条下界为0，上界为swg[i][ j ]，费用为1的边。
根据上述的构图，新添超级源点SS和超级汇点ST，根据模型，转化为下界均为0的网络流。最后，直接求解费用流即可。
#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;
// 费用流模板，封装在namespace里，避免变量，函数冲突
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; // 边数统计
int head[maxnode],path[maxnode],pre[maxnode],F[maxnode];
int o[200000]; // spfa队列，开的较大，如果不够可改成循环队列
bool vis[maxnode]; // spfa判断是否点在队列里
void init() // 初始化，多组数据必须调用
{
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的最小费用路径，N是网络流结点最后一个编号
{
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) // 找到路径后，得到流量和费用
{
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) // 建图后求最小费用最大流
{
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个状态，表示行和列，num表示点的编号
int SS=++num,ST=++num;
int sumdown=0; // 下届的和
fyl::init(); // 初始化
Mem(g,0); // 统计初始矩阵每个状态的1的个数
Mem(swg,0); // 统计状态间的交换次数，用于压缩边
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; // 频繁出现，先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; // 最大流要等于下届可，否则无解
return cost; // 返回有解的情况下的最小费用
}
int main(int argc, char* argv[])
{
for (; scanf("%d",&N)!=EOF; )
{
int ans=Done();
printf("%d\n",ans);
}
return 0;
}
