UVA1104 芯片难题 Chips Challenge 题解

Description

题目链接

有一个 $N \times N$ 的棋盘，可以在上面放棋子。

有些格子不能放棋子，有些格子必须放棋子，剩下的格子随意。

要求放好棋子之后满足如下两条要求：

1. 第 $i$ 行和第 $i$ 列的棋子数目必须一样多。$(1\leq i \leq N)$
2. 第 $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

#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<<11,nAB){
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;
}