https://darkbzoj.cf/problem/2673
有一个芯片，芯片上有N*N（1≤N≤40）个插槽，可以在里面装零件。
有些插槽不能装零件，有些插槽必须装零件，剩下的插槽随意。
要求装好之后满足如下两条要求：
1、第 i 行和第 i 列的零件数目必须一样多（1≤i≤N）。
2、第 i 行的零件数目不能超过总的零件数目的 A/B（1≤i≤N，0≤A≤B≤1000，B≠0）。
求最多可以另外放多少个零件（就是除掉必须放的）。如果无解输出impossible。
zkw费用流就是像跑最大流一样跑费用流，可以并行处理使得稠密图和二分图速度变快（据说）。
棋盘图依然是把横纵坐标拆成2n个点，每一个棋子可以用其横坐标到纵坐标的一条路表示。
棋盘上放最多的棋子相当于所有位置放上棋子后去掉最少的棋子，最小费用流处理就是给每一个可以去掉的棋子一个固定费用(1)。
i行和i列保留零件数目一样多就是从横坐标的i点到纵坐标的i点连一条费用为0流量固定为w的路。 w一定时，每一行每一列保留棋子的数量一定<=w。w上限是n所以我们可以枚举w建n次图跑网络流。
此时的最大流最小费用就是条件w下可以去掉的棋子数量的最小值（不仅要验证满足题目中的要求2，还要验证最大流=所有可以放棋子的位置的数量，因为保留棋子数量有时候可能小于某行列C的数量）（如果这个w跑最大流最小费用的方案不合法，那么就不存在w的合法条件）。
这个建n次图的方法有点像noip2017的那道搜索题目 NOIP2017 D2T2宝藏 都是按层次找的想法。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define LL long long
const int maxn=;
int n,A,B;
char ch[][];
int han[]={},shu[]={},sum,num,S,T,mx,cnt;
struct nod{
int x,y,next,v,co,rev;
}e[maxn];
int head[]={},tot=;
void init(int x,int y,int v,int co){
e[++tot].y=y;e[tot].x=x;e[tot].v=v;e[tot].co=co;e[tot].next=head[x];e[tot].rev=tot+;head[x]=tot;
e[++tot].y=x;e[tot].x=y;e[tot].v=;e[tot].co=-co;e[tot].next=head[y];e[tot].rev=tot-;head[y]=tot;
}
queue<int>q;
int dis[]={};bool vis[]={};
bool SPFA(){
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
mx=dis[];
q.push(S);vis[S]=;dis[S]=;
while(!q.empty()){
int x=q.front(),y;q.pop();vis[x]=;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;
if(e[i].v>&&dis[y]>dis[x]+e[i].co){
dis[y]=dis[x]+e[i].co;
if(!vis[y]){
q.push(y);vis[y]=;
}
}
}
}
return dis[T]!=mx;
}
int dfs(int x,int val){
if(x==T){
cnt+=dis[T]*val;
return val;
}
int liu=,tv,y;vis[x]=;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;
if(vis[y])continue;
if(e[i].v>&&dis[y]==dis[x]+e[i].co){
vis[y]=;
tv=dfs(y,min(val-liu,e[i].v));
liu+=tv;e[i].v-=tv;e[e[i].rev].v+=tv;
if(liu==val)break;
}
}
return liu;
}
int main(){
int C=;
while(~scanf("%d%d%d",&n,&A,&B)){
if(n==&&A==&&B==)break;
++C;
memset(han,,sizeof(han));memset(shu,,sizeof(shu));
sum=;cnt=;S=n*+;T=S+;
int zz=,ans=-;
for(int i=;i<n;i++){
scanf("%s",ch[i]);
for(int j=;j<n;j++){
if(ch[i][j]!='/'){
++han[i+];++shu[j+];++sum;
if(ch[i][j]=='C')++zz;
}
}
}
for(int w=;w<=n;w++){
tot=;memset(head,,sizeof(head));
for(int i=;i<=n;i++){
init(S,i,han[i],);
init(i+n,T,shu[i],);
init(i,i+n,w,);
for(int j=;j<=n;j++){
if(ch[i-][j-]=='.')init(i,j+n,,);
}
}int num=;cnt=;
while(SPFA()){memset(vis,,sizeof(vis));num+=dfs(S,sum);}
if(num==sum&&w*B<=(sum-cnt)*A)ans=max(ans,sum-cnt);
}cout<<endl;
if(ans==-)printf("Case %d: impossible\n",C);
else printf("Case %d: %d\n",C,ans-zz);
}
return ;
}