「bzoj3961」「WF2011」Chips Challenge - 网络流二维模型+流量平衡

题目大意

    在一个$n*n$的网格里放部件，有一些格子已经放置，有一些格子不能放置。要求第$x$行的部件数等于第$x$列，同时要求任意行列的部件数不超过总数的$\frac AB$。最大化数目。

---

题目分析

对行列的限制比较特殊，属于行列限制与总数的混合限制。
考虑使用流量平衡模型。
同时这是一个对二维棋盘的行列限制，可以使用二维模型：建立二分图，一边是行一边是列，若$(x,y)$有部件则从行$x$往列$y$连边。
枚举每一行的最大部件数$lim$，将流量平衡限制在$lim$。
若原图$(x,y)$已有部件，则从行$x$往列$y$连一条容量为$1$，费用为CHOSE_MAX的边，若$(x,y)$可以放部件，则从行$x$往列$y$连一条容量为$1$，费用为$1$的边。
这个CHOSE_MAX是为了让已有的部件必定会被选择使用的（最大费用最大流）。
在流量平衡的模型下，我们可以在满足要求时计算出可以再安装的组件数目cost % CHOSE_MAX。
这个CHOSE_MAX可以选一个相对于原图较大的值，比如$5000\gt 40\times 40$。

跑最大费用最大流在满足限制的时候统计答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=105;
 
struct Edge {
	int from,to,cap,flow,cost;
	Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};
 
struct zkw_CostFlow {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool inque[maxn],vst[maxn];
	int a[maxn],path[maxn];
	LL dist[maxn];
	int flow;
	LL cost;
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	int AddEdge(int x,int y,int v,int f) {
		edges.push_back(Edge(x,y,v,0,f));
		edges.push_back(Edge(y,x,0,0,-f));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
		return m-2;
	}
	bool spfa() {
		for(int i=1; i<=n; i++)dist[i]=-LLONG_MAX/2;
		memset(inque,0,sizeof(inque));
		dist[t]=0;
		inque[t]=1;
		deque<int>Q;
		Q.push_back(t);
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop_front();
			inque[Now]=0;
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(dist[Next]<dist[Now]+e.cost&&e.cap>e.flow) {
					dist[Next]=dist[Now]+e.cost;
					if(!inque[Next]) {
						inque[Next]=1;
						if(!Q.empty()&&dist[Next]>dist[Q.front()])Q.push_front(Next);
						else Q.push_back(Next);
					}
				}
			}
		}
		return dist[s]>-LLONG_MAX/2;
	}
	int dfs(int Now,int a) {
		if(vst[Now])return 0;
		if(Now==t||a==0)return a;
		int flow=0;
		vst[Now]=1;
		for(int id:G[Now]) {
			Edge& e=edges[id];
			int Next=e.to;
			if(dist[Now]-e.cost!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				cost+=(LL)nextflow*e.cost;
				e.flow+=nextflow;
				edges[id^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		flow=cost=0;
		while(spfa()) {
			memset(vst,0,sizeof(vst));
			flow+=dfs(s,INT_MAX);
		}
		return flow;
	}
} zkw;

const int CHOSE_MAX=5000;
int t,n,A,B,Max,num_must,ans;
char map[45][45];

void Clear() {
	num_must=Max=0;
	ans=-1;
}

int main() {
	while(true) {
		n=Get_Int();
		A=Get_Int();
		B=Get_Int();
		if(n+A+B==0)break;
		Clear();
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++) {
				char ch=' ';
				while(ch!='.'&&ch!='/'&&ch!='C')ch=getchar();
				map[i][j]=ch;
				if(ch=='C')num_must++;
			}
		for(int i=1; i<=n; i++) {
			int sum1=0,sum2=0;
			for(int j=1; j<=n; j++) {
				sum1+=map[i][j]=='C';
				sum2+=map[j][i]=='C';
			}
			Max=max(Max,max(sum1,sum2));
		}
		int S=2*n+1,T=2*n+2;
		for(int lim=Max; lim<=n; lim++) {
			zkw.init(T);
			for(int i=1; i<=n; i++)
				for(int j=1; j<=n; j++) {
					if(map[i][j]=='.')zkw.AddEdge(i,n+j,1,1);
					if(map[i][j]=='C')zkw.AddEdge(i,n+j,1,CHOSE_MAX+1);
				}
			for(int i=1; i<=n; i++) {
				zkw.AddEdge(S,i,lim,0);
				zkw.AddEdge(i,n+i,INT_MAX/2,0);
				zkw.AddEdge(n+i,T,lim,0);
			}
			zkw.maxflow(S,T);
			if(zkw.cost/CHOSE_MAX!=num_must)continue;
			int cnt=zkw.cost%CHOSE_MAX;
			if(cnt*A>=lim*B)ans=max(ans,cnt);
		}
		if(~ans)printf("Case %d: %d\n",++t,ans-num_must);
		else printf("Case %d: impossible\n",++t);
	}
	return 0;
}