题目大意
一个\(n\)行\(n\)列的字符矩阵\(S\),每个位置有\(C,.,/\)三种字符,需要往\(.\)中填入尽量多的\(W\)使得,\(\forall i,\sum_{j=1}^n[S_{i,j}=W|S_{i,j}=C]=\sum_{j=1}^n[S_{j,i}=W|S_{j,i}=C]\),设总共填入\(m\)个\(W\),还要满足\(\forall i,\sum_{j=1}^n[S_{i,j}=W|S_{i,j}=C]\le m\frac{A}{B}\)
题解
这种玄学的条件,一看就应该想到网络流
第一个条件,可以把第\(i\)行第\(i\)列,看成一个点,然后用流到\(i\)的流量,和流出\(i\)的流量,来表示第\(i\)行减去第\(i\)列的差,条件是相等,所以我们希望他们的差为\(0\)
设\(r_i\)表示行减列的差,将\((i,j)\)填入一个\(W\),会使得,\(r_i++,r_j--\),那么我们就让\(j\)向\(i\)连一条流量为\(1\),费用为\(1\)的边
然后初始时,如果\(r_i>0\),就让\(S\)向\(i\)连流量为\(r_i\)费用为\(0\)的边,\(r_i<0\)就让\(i\)向\(T\)连一条流量为\(-r_i\)的边
第二个条件比较难弄,因为\(m\)会随着填入的\(W\)而变动,由于\(n\)比较小,可以直接枚举\(m\),然后限制就变成了,每一行填入的\(W\)小于等于某个值,这个拆点处理,把\(i\)拆成\(i\)和\(i+n\),连一条\(i\)向\(i+n\)的边,流量就是\(W\)的上限,前面的连边也要稍改一下
然后就要跑个最大流最大费用
但是仔细思考,发现,它只有\(S\)到别的点的边需要到上限,其他的边也可以通过只流可行流的方式来使费用更大,而且还存在正环问题,题目就变成了,上下界可行流最大费用问题,可以对原图做若干转化来解决
但还有一种更好的方案,就是反过来做,假设\(.\)已经全部填上了\(W\),然后跑最小费用,然后把\(.\)的数量减去最小费用就行,正环问题还有可行流问题就解决了,但是由于第二个条件,每行的\(W\)变成\(.\)的数量有下界,也就是问题就是上下界最大流最小费用,做点转化就解决了
我写完之后一直超时,后来发现可以加个优化,不用每个\(m\)都枚举,可以直接让\(m\)直接跳到费用流的结果,因为\(m\)不会比这个更大,然后就跑的飞快了
代码
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
void read(int &res)
{res=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=5e3+100,M=5e4+100,inf=2147483647;
int st[N+10],tot=1;
struct edge
{int to,last,flow,val;
}e[M<<1|1];
void add(int a,int b,int c,int d)
{e[++tot].to=b;e[tot].flow=c;e[tot].val=d;e[tot].last=st[a];st[a]=tot;
}
void Add(int a,int b,int c,int d){add(a,b,c,d),add(b,a,0,-d);}
queue<int> q;int dis[N+10],pre[N+10],pree[N+10],flow[N+10];
bool vis[N+10];
bool spfa(int s,int t)
{for(int i=s;i<=t;i++) dis[i]=inf,pre[i]=pree[i]=-1,flow[i]=0;vis[s]=true,dis[s]=0,flow[s]=inf,q.push(s);for(int u;!q.empty();){u=q.front(),q.pop(),vis[u]=false;for(int i=st[u],v;i!=0;i=e[i].last){v=e[i].to;if(e[i].flow&&dis[v]>dis[u]+e[i].val){dis[v]=dis[u]+e[i].val,pre[v]=u,pree[v]=i,flow[v]=min(flow[u],e[i].flow);if(!vis[v]) q.push(v),vis[v]=true; }}}return pre[t]!=-1;
}
int resf,resc;
void MCMF(int s,int t)
{while(spfa(s,t)){resc+=dis[t]*flow[t],resf+=flow[t];int u=t;while(u!=s){e[pree[u]].flow-=flow[t],e[pree[u]^1].flow+=flow[t];u=pre[u];}}
}
const int mn=50;
int n,A,B;
char s[mn+1][mn+1];
int row[N+10],col[N+10];
int main()
{
// freopen("a.in","r",stdin);int tt=0;while(1){tt++; scanf("%d %d %d",&n,&A,&B);if(n==0) break;for(int i=1;i<=n;i++)scanf("%s",s[i]+1),row[i]=col[i]=0;int S=0,T=2*n+1,sum=0,sumc=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(s[i][j]=='C'||s[i][j]=='.')row[i]++,col[j]++;if(s[i][j]=='.')sum++;if(s[i][j]=='C')sumc++;}
// for(int i=1;i<=n;i++)
// {
// printf("%d %d\n",row[i],col[i]);
// }
// printf("sum1 %d\n",sum);
// printf("sum %d\n",n*n*n*A/B);bool flag=false;for(int m=sum;m>=0;m--){
// printf("%d\n",m);tot=1;for(int i=S;i<=T;i++) st[i]=0;int maxflow=0;for(int i=1;i<=n;i++){if(row[i]-col[i]>0)Add(S,i,row[i]-col[i],0),maxflow+=row[i]-col[i];elseAdd(i,T,col[i]-row[i],0);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(s[i][j]=='.')Add(i+n,j,1,1);for(int i=1;i<=n;i++){if((m+sumc)*A/B<row[i]){
// puts("fuc");Add(S,i+n,row[i]-(m+sumc)*A/B,0);Add(i,T,row[i]-(m+sumc)*A/B,0);maxflow+=row[i]-(m+sumc)*A/B;}Add(i,i+n,inf,0);}resf=resc=0;MCMF(S,T);
// printf("%d %d\n",resf,resc);if(resf==maxflow&&sum-resc==m){printf("Case %d: %d\n",tt,m);flag=true;break;}m=min(sum-resc+1,m);}if(!flag){printf("Case %d: impossible\n",tt);}}return 0;
}