Description
有一个 $N \times N$ 的棋盘，可以在上面放棋子。
有些格子不能放棋子，有些格子必须放棋子，剩下的格子随意。
要求放好棋子之后满足如下两条要求：
- 第 $i$ 行和第 $i$ 列的棋子数目必须一样多。$(1\leq i \leq N)$
- 第 $i$ 行的棋子数目不能超过总的棋子数目的 $\frac{A}{B}$。$(1\leq i \leq N)$
求最多可以另外放多少个棋子（就是除掉必须放的）。如果无解输出 impossible。
$1\leq N \leq 40,1\leq A\leq B\leq 1000$
Solution
我们可以考虑补集思想。
考虑如果一开始把所有可以放的格子不管三七二十一都放上棋子。
那么题目就转化为至少从中除掉多少个棋子，使其满足题目条件。
但问题来了，我们既不知道棋子的总个数，也不知道每一行的个数。
既然是要求最少，那么我们可以先枚举每一行最多的棋子的个数，然后跑一遍费用流，计删掉一个棋子的花费为 $i$，那么问题就转化为求最小费用最大流。
考虑如何建图，
首先将超级源点 $S$ 连向 $i$ 一条流量为 $sumx[i]$（表示该行的可以放的棋子数量），费用为 $0$ 的边，表示该行一开始就可以有 $sumx[i]$ 个棋子。
再将每一列 $i+n$ 连向超级汇点 $T$ 一条流量为 $sumy[i]$，费用为 $0$ 的边，表示该列最多可以放置 $sumy[i]$。
然后将每一行 $i$ 与对应的列 $i+n$ 连一条流量为 $flow$（表示枚举到的对多流量），费用为 $0$ 的边，表示每一行每一列的放置棋子的个数应该相等。
然后考虑如果第 $i$ 行 $j$ 列是 '.'，表示可以放也可以不放，那么我们就可以 $i$ 连一条 $j+n$ 的边，流量为 $1$，费用为 $1$。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& #define gc getchar #define D isdigit(c=gc()) #define pc(c) putchar((c)) #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;} Ts I void read(Ty& x,Ar&... y){read(x),read(y...);} Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);} Tp I void writeln(Cn Ty& x){write(x),pc('\n');} }using namespace FastIO; const int N=1010; int n,A,B,sum,used,sumx[N],sumy[N],s[N][N],S,T,fir[N<<1],nxt[N*N<<1],son[N*N<<1],w[N*N<<1],cost[N*N<<1],tot=1,Ans,Cost,Max=-1,inf=2e9,dis[N<<1],vis[N<<1],Case; I int Read_char(){char c=gc();W(c^'/'&&c^'.'&&c^'C') c=gc();return c=='/'?-1:c=='C';} I void Add(CI x,CI y,CI z,CI c){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c;nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0,cost[tot]=-c;} queue<int> q; #define to son[i] struct Edge{int son,id;}pre[N<<1]; I bool bfs(){ W(!q.empty()) q.pop();q.push(S);memset(dis,63,sizeof(dis));inf=dis[0];dis[S]=0;memset(vis,0,sizeof(vis));W(!q.empty()){ RI u=q.front(),i;q.pop();for(i=fir[u];i;i=nxt[i]) if(w[i]>0&&dis[to]>dis[u]+cost[i]) dis[to]=dis[u]+cost[i],pre[to]=(Edge){u,i},!vis[to]&&(q.push(to),vis[to]=1);vis[u]=0;}return dis[T]<inf; } I void EK(){Ans=Cost=0;RI Min=inf,i;W(bfs()){Min=inf;for(i=T;i^S;i=pre[i].son) Min=min(Min,w[pre[i].id]);for(i=T;i^S;i=pre[i].son) w[pre[i].id]-=Min,w[pre[i].id^1]+=Min;Ans+=Min,Cost+=Min*dis[T];}return ;} int main(){ RI i,j,k;W(read(n,A,B),memset(sumx,0,sizeof(sumx)),memset(sumy,0,sizeof(sumy)),S=sum=sum=used=0,T=n<<1|1,n||A||B){ for(i=1;i<=n;i++) for(j=1;j<=n;j++) s[i][j]=Read_char();for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(s[i][j]>=0) sum++,sumx[i]++,sumy[j]++,used+=s[i][j];for(Max=-1,k=0;k<=n;k++){ for(memset(fir,0,sizeof(fir)),tot=1,i=1;i<=n;i++) for(Add(S,i,sumx[i],0),Add(i+n,T,sumy[i],0),Add(i,i+n,k,0),j=1;j<=n;j++) !s[i][j]&&(Add(i,j+n,1,1),0); EK();if(Ans==sum&&k*B<=(sum-Cost)*A) Max=max(Max,sum-Cost); }printf("Case %d: ",++Case);if(~Max) writeln(Max-used);else puts("impossible"); }return 0; } |
