两个条件都不太好处理
每行放置的个数实际很小，枚举最多放x
但还是不好放
考虑所有位置先都放上，然后删除最少使得合法
为了凑所有的位置都考虑到，把它当最大流
但是删除最少，所以最小费用
行列相关，左行点，右列点
S到行，流“能填位置”费0
列到T，流“能填位置”费0
i行到i列，流x，即枚举的最大个数
空位(i,j)，i行连j列，流1费0
最小费用最大流
意义：流过i行到i列的流量，象征留下一个芯片
流过费用为1的，象征把这个芯片删除。
最大流保证所有位置都考虑到了
最小费用使得最少。
可以发现最后的结果一定满足条件1
条件2？
最大流为flow，费用为cos，总共的位置（多出来的+必填）=sum
放置了tot=sum-cos
如果有x/tot<=A/B那么更新ans=max(ans,tot)
x一定时，tot越大，越可能比A/B小。和最小费用相符。
虽然可能x过大，但是答案一定可以枚举到。
代码：
#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=42; const int P=86; const int inf=0x3f3f3f3f; int n,A,B; struct node{ int nxt,to; int c,w; }e[2*(N*N+2*N)+233]; int hd[P],cnt=1; int s,t; void add(int x,int y,int w,int c){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].c=c; e[cnt].w=w;hd[x]=cnt; e[++cnt].nxt=hd[y]; e[cnt].to=x; e[cnt].c=-c; e[cnt].w=0;hd[y]=cnt; } int dis[P]; bool in[P]; int incf[P],pre[P]; queue<int>q; int ans,flow,cos; int l[N],h[N]; char mp[N][N]; bool spfa(){ memset(dis,inf,sizeof dis); memset(pre,0,sizeof pre); while(!q.empty()) q.pop(); dis[s]=0; incf[s]=inf; q.push(s); while(!q.empty()){ int x=q.front();q.pop(); in[x]=0; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(e[i].w){ if(dis[y]>dis[x]+e[i].c){ dis[y]=dis[x]+e[i].c; pre[y]=i; incf[y]=min(incf[x],e[i].w); if(!in[y]){ in[y]=1; q.push(y); } } } } } if(dis[t]==inf) return false; return true; } void upda(){ int x=t; while(pre[x]){ e[pre[x]].w-=incf[t]; e[pre[x]^1].w+=incf[t]; x=e[pre[x]^1].to; } flow+=incf[t]; cos+=dis[t]*incf[t]; } void EK(int lim){ cos=0;flow=0; memset(hd,0,sizeof hd); cnt=1; s=0,t=2*n+1; for(reg i=1;i<=n;++i) { add(s,i,l[i],0); add(i+n,t,h[i],0); add(i,i+n,lim,0); } for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ if(mp[i][j]=='.') add(i,j+n,1,1); } } while(spfa()) upda(); } void clear(){ ans=-2333; for(reg i=1;i<=n;++i) l[i]=n; for(reg j=1;j<=n;++j) h[j]=n; } int main(){ int o=0; while(1){ rd(n);rd(A);rd(B); if(n==0&&A==0&&B==0) break; ++o; clear(); int can=0; int alr=0; for(reg i=1;i<=n;++i){ scanf("%s",mp[i]+1); for(reg j=1;j<=n;++j){ if(mp[i][j]=='/') --l[i],--h[j]; else ++can; if(mp[i][j]=='C') ++alr; } } for(reg x=0;x<=n;++x){ EK(x); int tot=can-cos; if(flow==can&&A*tot>=x*B) ans=max(ans,tot); } ans-=alr; printf("Case %d: ",o); if(ans<0) printf("impossible"); else printf("%d",ans); puts(""); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/1/8 10:23:22 */
最小费用最大流可以考虑两个限制
最大流限制合法
费用流限制优秀