题意

有一个芯片，芯片上有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。

题解

一个比较简单粗暴的方法是枚举一共加上了多少个点
然后跑网络流验证
原来有的就看做一定要填
然后就相当于每一行/列最多填多少
然后如果满流就是合法

bool check (int x)//加上多少个 
{num=1;memset(last,-1,sizeof(last));for (int u=1;u<=n;u++)for (int i=1;i<=n;i++)if (ss[u][i]=='.')//这个点可以填init(u,i+n,1,1);int sum=(tot+x)*a/b;//不能超过这么多 for (int u=1;u<=n;u++)   {init(st,u,sum-A[u],0);init(u+n,ed,sum-B[u],0);init(u,u+n,sum,0);}ans=0;while (SPFA()) lalal();if (ans!=x) return false;for (int u=last[st];u!=-1;u=e[u].last)if (e[u].z!=0) return false;return true;
}

但是我们发现，这样的话要跑$n^2$次网络流，显然会T
于是我们考虑到，我们的sum
其实最大范围只会到$n+A(B)[i]$
也就是nn<script type="math/tex" id="MathJax-Element-98">n</script>的范围的
然后由生面判满流可以知道，最终的答案其实就是流量
于是我们可以枚举sum
这样就只用跑n次网络流，就可以通过了

CODE:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX=(1<<28);
const int N=45*2;
int n,a,b;
int A[N],B[N];
char ss[N][N];
struct qt
{int x,y,z,z1,last;//流量 费用 
}e[N*N];int num,last[N];
int st,ed;
void init (int x,int y,int z,int z1)
{
// printf("\n%d %d %d %d",x,y,z,z1);num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].z1=z1;e[num].last=last[x];last[x]=num;swap(x,y);z=0;z1=-z1;num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].z1=z1;e[num].last=last[x];last[x]=num;
}
int from[N];
int f[N];
bool in[N];
bool SPFA ()
{memset(in,false,sizeof(in));memset(from,-1,sizeof(from));for (int u=1;u<=ed;u++) f[u]=-MAX;queue<int> q;q.push(st);f[st]=0;in[st]=true;while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (e[u].z>0&&f[y]<f[x]+e[u].z1){f[y]=f[x]+e[u].z1;from[y]=u;if (in[y]==false){in[y]=true;q.push(y);}}}in[x]=false;}return from[ed]!=-1;
}
int ans=0;
void lalal ()
{int x=from[ed],t=MAX;while (x!=-1){t=min(t,e[x].z);x=from[e[x].x];}x=from[ed];while (x!=-1){ans=ans+t*e[x].z1;e[x].z-=t;e[x^1].z+=t;x=from[e[x].x];}return ;
}
int tot=0;//一开始有多少个 
bool check (int sum)//这个枚举的是sum 
{num=1;memset(last,-1,sizeof(last));for (int u=1;u<=n;u++)for (int i=1;i<=n;i++)if (ss[u][i]=='.')//这个点可以填init(u,i+n,1,1);for (int u=1;u<=n;u++)   {init(st,u,sum-A[u],0);init(u+n,ed,sum-B[u],0);init(u,u+n,sum,0);}ans=0;while (SPFA()) lalal();int x=ans;if ((tot+x)*a/b!=sum) return false;for (int u=last[st];u!=-1;u=e[u].last)if (e[u].z!=0) return false;printf("%d %d\n",x,sum);return true;
}
int main()
{
// freopen("chips.in","r",stdin);//freopen("chips1.out","w",stdout);int Case=0;while (true){memset(A,0,sizeof(A));memset(B,0,sizeof(B));tot=0;scanf("%d%d%d",&n,&a,&b);if (n+a+b==0) break;st=2*n+1;ed=st+1;for (int u=1;u<=n;u++){scanf("%s",ss[u]+1);for (int i=1;i<=n;i++)if (ss[u][i]=='C'){A[u]++;B[i]++;tot++;} }printf("Case %d: ", ++Case);bool tf=false;for (int u=2*n;u>=0;u--)if (check(u)){tf=true;break;}if (!tf) printf("impossible\n");}return 0;
}