UVA1104 芯片难题 Chips Challenge 题解
Description
题目链接
有一个 N times N 的棋盘，可以在上面放棋子。
有些格子不能放棋子，有些格子必须放棋子，剩下的格子随意。
要求放好棋子之后满足如下两条要求：
- 第 i 行和第 i 列的棋子数目必须一样多。(1leq i leq N)
- 第 i 行的棋子数目不能超过总的棋子数目的 frac{A}{B}。(1leq i leq N)
求最多可以另外放多少个棋子（就是除掉必须放的）。如果无解输出 impossible。
1leq N leq 40,1leq Aleq Bleq 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
代码语言：javascript复制#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 '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;
}
