题意
给出一个n*n的网格,有些格子必须染成黑色,有些格子必须染成白色,其他格子可以染成黑色或者白色.要求最后第i行的黑格子数目等于第i列的黑格子数目,且某一行/列的格子数目不能超过格子总数的A/B.
(把某个格子染黑等价于"在这个格子放一个芯片")
n<=40
分析
假设一共用了X个芯片(包括'C'和'.'两种情况下放的),那么每行每列最多放的芯片个数Y=X*A/B可以算出来.发现不同的Y值最多有40个,我们可以考虑枚举每个Y值,Y值确定之后X有一个下界,我们考虑此时最多放下的芯片个数能否达到这个下界即可.
建出2n个点分别代表n行n列,第i行向第j列连一条边.
如果(i,j)是'C',那么这条边的上下界均为1.
如果(i,j)是'.',那么这条边的上下界为[0,1]
如果(i,j)是'',那么上下界均为0(相当于没有边).
然后我们从第i列到第i行连一条下界为0上界为Y的边.
这张网络上一个满足流量平衡的流就对应一个合法的方案.我们要最大化代表格子的n*n条边里有流量的边数.不妨把这n*n条边的费用都设为1,我们现在只需要找出一个满足流量上下界限制且费用最大的循环流.
接下来我的做法就纯属乱搞了,应该可以换成更加有理有据的上下界费用流
首先考虑满足流量上下界限制.套用上下界网络流中循环可行流那一套理论即可.
现在跑出来的可行流不一定是费用最大的,残量网络里可能有正权圈.所以...我们暴力跑spfa,每次增广一个残量网络上的正权圈,直到不存在正权圈,就找到了最大费用的可行流...(我也不知道这为什么是对的,求证明或证伪,不过它确实能过23333)
当然这个算法很慢,我们可以利用这张图的特性,手动消一些正权圈,细节看代码.
我可能还需要学习一个有上下界的费用流
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=85,maxm=100005;
struct edge{
int to,next,w,cost;
}lst[maxm];int len=0,first[maxn],_first[maxn];
void addedge(int a,int b,int w,int cost){
lst[len].to=b;lst[len].next=first[a];lst[len].w=w;lst[len].cost=cost;first[a]=len++;
lst[len].to=a;lst[len].next=first[b];lst[len].w=0;lst[len].cost=-cost;first[b]=len++;
}
int ans=0,maxans=-1;
int totflow[maxn];
int pos[maxn][maxn];
void Add(int a,int b,int lo,int hi,int cost){
pos[a][b]=len;
ans+=lo*cost;totflow[a]-=lo;totflow[b]+=lo;
addedge(a,b,hi-lo,cost);
}
int n,A,B;
char str[maxn][maxn];
int s,t,q[maxn],dis[maxn],vis[maxm],prt[maxn],fr[maxn],head,tail,T;
bool bfs(){
head=tail=0;vis[s]=++T;dis[s]=1;q[tail++]=s;
while(head!=tail){
int x=q[head++];
for(int pt=first[x];pt!=-1;pt=lst[pt].next){
if(lst[pt].w&&vis[lst[pt].to]!=T){
vis[lst[pt].to]=T;dis[lst[pt].to]=dis[x]+1;q[tail++]=lst[pt].to;
}
}
}
if(vis[t]==T)memcpy(_first,first,sizeof(first));
return vis[t]==T;
}
int dfs(int x,int lim){
if(x==t)return lim;
int flow=0,a;
for(int pt=_first[x];pt!=-1;pt=lst[pt].next){
_first[x]=pt;
if(lst[pt].w&&dis[lst[pt].to]==dis[x]+1&&(a=dfs(lst[pt].to,min(lst[pt].w,lim-flow)))){
lst[pt].w-=a;lst[pt^1].w+=a;flow+=a;ans+=a*lst[pt].cost;
if(flow==lim)return flow;
}
}
return flow;
}
int dinic(){
int flow=0,x;
while(bfs()){
while(x=dfs(s,0x3f3f3f3f)){
flow+=x;
}
}
return flow;
}
void del(int x){
for(int pt=first[x];pt!=-1;pt=lst[pt].next)lst[pt].w=lst[pt^1].w=0;
}
bool inq[maxn];
int f[maxn];
bool spfa(){
for(int i=1;i<=2*n;++i)inq[i]=false;
head=tail=0;++T;
for(int i=1;i<=n;++i){
dis[i]=0;q[tail++]=i;vis[i]=T;inq[i]=true;prt[i]=-1;
f[i]=1;
}
bool flag=false;
while(head!=tail){
int x=q[head++];if(head==maxn)head=0;inq[x]=false;
for(int pt=first[x];pt!=-1;pt=lst[pt].next){
if(f[x]>2*n){
flag=true;break;
}
if(lst[pt].w==0)continue;int y=lst[pt].to;
if(vis[y]!=T||dis[y]<dis[x]+lst[pt].cost){
vis[y]=T;
dis[y]=dis[x]+lst[pt].cost;f[y]=f[x]+1;
prt[y]=pt;
if(!inq[y]){
inq[y]=true;q[tail++]=y;
if(tail==maxn)tail=0;
}
}
}
}
if(flag){
for(int i=1;i<=2*n;++i){
if(f[i]>2*n){
vis[i]=++T;
int pos=i;
for(int pt=prt[i];vis[lst[pt^1].to]!=T;pt=prt[lst[pt^1].to]){
vis[lst[pt^1].to]=T;pos=lst[pt^1].to;
}
++T;
for(int pt=prt[pos];vis[pt]!=T;pt=prt[lst[pt^1].to]){
ans+=lst[pt].cost;lst[pt].w--;lst[pt^1].w++;vis[pt]=T;
}
break;
}
}
return true;
}else
return false;
}
void addflow(int pt){
lst[pt].w--;lst[pt^1].w++;ans+=lst[pt].cost;
}
bool maxcost(){
int tmpsum=0;
s=0;t=2*n+1;
for(int i=1;i<=n*2;++i){
if(totflow[i]>0){
addedge(s,i,totflow[i],0);
tmpsum+=totflow[i];
}else{
addedge(i,t,-totflow[i],0);
}
}
if(dinic()!=tmpsum)return false;
del(s);del(t);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(pos[i][n+j]==-1||pos[j][n+i]==-1||pos[n+i][i]==-1||pos[n+j][j]==-1)continue;
if(i!=j&&lst[pos[i][n+j]].w&&lst[pos[j][n+i]].w&&lst[pos[n+i][i]].w&&lst[pos[n+j][j]].w){
addflow(pos[i][n+j]);addflow(pos[j][n+i]);addflow(pos[n+i][i]);addflow(pos[n+j][j]);
}
}
}
while(spfa());
return true;
}
bool check(int uplim){
ans=0;memset(first,-1,sizeof(first));len=0;
memset(pos,-1,sizeof(pos));
for(int i=1;i<=n*2;++i)totflow[i]=0;
for(int i=1;i<=n;++i)Add(n+i,i,0,uplim,0);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(str[i][j]=='C'){
Add(i,n+j,1,1,1);
}else if(str[i][j]=='.'){
Add(i,n+j,0,1,1);
}
}
}
if(maxcost()){
int lim2=ceil(uplim/double(A)*double(B));
if(ans>=lim2&&ans>=maxans)maxans=ans;
}
}
int main(){
int tests=0;
while(scanf("%d%d%d",&n,&A,&B),n!=0){
maxans=-1;ans=0;
++tests;
for(int i=1;i<=n;++i)scanf("%s",str[i]+1);
int init=0,l=0,r=0;
int sum=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(str[i][j]=='C'){
init++;sum++;
}else if(str[i][j]=='.')sum++;
}
}
if(1.0/n>A/double(B)){
if(init!=0)printf("Case %d: impossible
",tests);
else printf("Case %d: 0
",tests);
continue;
}
double bound=min((int)(sum*1.0*A/B),n);
for(int uplim=bound;uplim>=0;--uplim){
check(uplim);if(maxans!=-1)break;
}
if(maxans!=-1)printf("Case %d: %d
",tests,maxans-init);
else printf("Case %d: impossible
",tests);
}
return 0;
}