数据范围看起来很像网络流诶(滚那
因为限制多而且强，数据范围也不大，我们考虑不直接求答案，而是转化为判定问题
可以发现第二个限制相对好满足，我们直接枚举这个限制就可以。具体来说是枚举所有行中的最大值$x$，然后下面那个式子移项就可以得到$a*tot>=b*x$，其中tot表示芯片的总数
然后发现第一个限制还是很强，不好满足。怎么办呢？正难则反，转化成补集的问题：先把所有能安的芯片都安了，然后扣出来合法的答案
那么现在我们要扣掉的芯片尽量少，同时还要先保证扣出来的结果合法，那考虑用最小费用最大流，用最大流的限制使得答案合法，用最小费用求答案
具体来说我们这样建图(下面再解释)：
①把原图拆成行和列共n个点
②记录每行每列最多的芯片个数(包括已经有的和空位)，从原点向一边连边，另一边向汇点连边(这里为了方便我默认原点向行连，汇点向列连)。容量为芯片个数，费用为零(这个不用解释吧)
③第i行向第i列连容量为我们枚举的答案的边，表示至多留下这些芯片，费用仍然为零
④对于每个空位(x,y)，从第x行向第y列连流量为1费用为1的边，表示同时从这一行一列扣掉一个芯片
然后跑最小费用最大流，当且仅当最大流等于芯片的最大总数(包括已经有的和空位))时更新答案，为什么？
因为最小费用最大流会优先保证满流，所以我们③中连的边相当于限制了每行每列的芯片个数一样，就满足了第一个限制，然后扣掉的加上剩下的等于总数才是合法的，所以这时候更新答案
大概就是这样，我觉得这题还是有点意思的=。=
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int B=50,N=4005,M=100005,inf=1e9; 7 int mxr[B],mxc[B],mapp[B][B]; char rd[B]; 8 int mflw[N],mcst[N],pren[N],pree[N],queu[N]; 9 int p[N],noww[2*M],goal[2*M],flow[2*M],cost[2*M]; 10 int n,a,b,s,t,id,ocp,tot,num,cnt,ans,maxf,minc; queue<int> qs; 11 void Link(int f,int t,int v,int c) 12 { 13 noww[++cnt]=p[f],p[f]=cnt; 14 goal[cnt]=t,flow[cnt]=v,cost[cnt]=c; 15 noww[++cnt]=p[t],p[t]=cnt; 16 goal[cnt]=f,flow[cnt]=0,cost[cnt]=-c; 17 } 18 void Setit() 19 { 20 memset(mxr,0,sizeof mxr); 21 memset(mxc,0,sizeof mxc); 22 ocp=tot=0,ans=-1,s=n*2+1,t=s+1; 23 for(int i=1;i<=n;i++) 24 { 25 scanf("%s",rd+1); 26 for(int j=1;j<=n;j++) 27 { 28 mapp[i][j]=rd[j],ocp+=rd[j]=='C'; 29 if(rd[j]!='/') mxr[i]++,mxc[j]++,tot++; 30 } 31 } 32 } 33 void Init(int st,int ed) 34 { 35 memset(mflw,0x3f,sizeof mflw); 36 memset(mcst,0x3f,sizeof mcst); 37 memset(queu,0,sizeof queu),pren[ed]=-1; 38 qs.push(st),queu[st]=true,mcst[st]=0; 39 } 40 bool SP(int st,int ed) 41 { 42 Init(st,ed); 43 while(!qs.empty()) 44 { 45 int tn=qs.front(); 46 qs.pop(),queu[tn]=false; 47 for(int i=p[tn],g;i;i=noww[i]) 48 if(mcst[g=goal[i]]>mcst[tn]+cost[i]&&flow[i]) 49 { 50 pree[g]=i,pren[g]=tn; 51 mcst[g]=mcst[tn]+cost[i]; 52 mflw[g]=min(mflw[tn],flow[i]); 53 if(!queu[g]) qs.push(g),queu[g]=true; 54 } 55 } 56 return ~pren[ed]; 57 } 58 void MCMF(int st,int ed) 59 { 60 while(SP(st,ed)) 61 { 62 maxf+=mflw[ed],id=ed; 63 minc+=mflw[ed]*mcst[ed]; 64 while(id!=st) 65 { 66 flow[pree[id]]-=mflw[ed]; 67 flow[pree[id]^1]+=mflw[ed]; 68 id=pren[id]; 69 } 70 } 71 } 72 int Solve(int x) 73 { 74 memset(p,0,sizeof p),cnt=1,maxf=minc=0; 75 for(int i=1;i<=n;i++) 76 Link(s,i,mxr[i],0),Link(i+n,t,mxc[i],0),Link(i,i+n,x,0); 77 for(int i=1;i<=n;i++) 78 for(int j=1;j<=n;j++) 79 if(mapp[i][j]=='.') Link(i,j+n,1,1); MCMF(s,t); 80 return maxf==tot?(a*(tot-minc)>=b*x?tot-ocp-minc:-1):-1; 81 } 82 int main() 83 { 84 while(scanf("%d%d%d",&n,&a,&b)!=EOF) 85 if(n||a||b) 86 { 87 Setit(); 88 for(int i=0;i<=n;i++) 89 ans=max(ans,Solve(i)); 90 printf("Case %d: ",++num); 91 ~ans?printf("%d ",ans):printf("impossible "); 92 } 93 else break; 94 return 0; 95 }