文章目錄

• 題目描述
• 解析
• 代碼

題目描述

有一個n*n的棋盤，可以在上面放棋子。
有些格子不能放棋子，有些格子必須放棋子，剩下的格子隨意。

要求放好棋子之后滿足如下兩條要求：

第 i 行和第 i 列的棋子數目必須一樣多。
第 i 行的棋子數目不能超過總的棋子數目的 a/b。

求最多可以另外放多少個棋子（除掉必須放的）。如果無解輸出 impossible。

解析

神仙題
這誰能想到是網絡流啊… qwq
考慮正難則反，考慮舍棄哪些棋子
對于一個可以放棄的棋子$(i,j)$，就從 i 連一條向 j ，流量1，費用1的邊。
然后對原點向每一行連一條流量是該行最多可以放置的棋子（包括必放和選放）
每列向匯點連同理的邊
然后考慮放置棋子，因為條件1的限制，就從 i 行向 i 列連一條費用是0的邊
這條邊的流量就代表著第 i 行/列的放置的棋子數
這樣就能使第i行和第i列選的棋子數相同
為了滿足條件2，暴力枚舉這條邊的最大容量判合法即可

代碼

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=105; const int M=2e6+100; const int mod=998244353; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,s,t; struct node{int to,nxt;ll cap,w; }p[M<<1]; int fi[N],cnt,cur[N]; void addline(int x,int y,ll cap,ll w){p[++cnt]=(node){y,fi[x],cap,w};fi[x]=cnt;p[++cnt]=(node){x,fi[y],0,-w};fi[y]=cnt; // printf(" %d->%d cap=%lld w=%lld\n",x,y,cap,w); } ll flow,cost; queue<int>q; ll dis[N]; bool vis[N]; bool spfa(){memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push(s);bool flag=0;while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap) continue;if(to==t) flag=1;if(dis[to]>dis[now]+p[i].w){dis[to]=dis[now]+p[i].w;if(!vis[to]){q.push(to);vis[to]=1;}}}}return flag; } ll dfs(int x,ll lim){if(x==t||!lim){cost+=lim*dis[t];return lim;}vis[x]=1;ll res=0;for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]||!p[i].cap||dis[to]!=dis[x]+p[i].w) continue;ll add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(lim) dis[x]=-1;vis[x]=0;return res; } void dinic(){flow=0;cost=0;while(spfa()){while(ll tmp=dfs(s,2e18)){flow+=tmp;//printf("tmp=%d\n",tmp);}}return; } char mp[50][50]; int a,b; bool flag; int heng[55],su[55]; int tot,ans,res; void work(int w){memset(fi,-1,sizeof(fi));cnt=-1;memset(heng,0,sizeof(heng));memset(su,0,sizeof(su));//printf("-----w=%d\n",w);s=2*n+1;t=s+1;tot=0;res=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]=='/') continue;heng[i]++;su[j]++;tot++;if(mp[i][j]=='.') addline(i,j+n,1,1);else res++;}}for(int i=1;i<=n;i++){addline(s,i,heng[i],0);addline(i+n,t,su[i],0);addline(i,i+n,w,0);}dinic(); // printf("flow=%d cost=%d tot=%d\n",flow,cost,tot);if(w*b<=(tot-cost)*a&&flow==tot){flag=1;ans=max(ans,tot-(int)cost);} } int main(){int o=0;while(1){flag=0;ans=0;n=read();a=read();b=read();if(n+a+b==0) break;for(int i=1;i<=n;i++) scanf(" %s",mp[i]+1);for(int i=0;i<=n;i++){work(i);}//work(1);o++;printf("Case %d: ",o);if(!flag) printf("impossible\n");else printf("%d\n",ans-res);}return 0; } /**/ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的YBTOJ：放置棋子（费用流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。