网站开发毕业实训总结,网络营销是什么大类,seo网站改版方案怎么写,小说主题+wordpress文章目录题目描述解析代码题目描述
有一个n*n的棋盘#xff0c;可以在上面放棋子。 有些格子不能放棋子#xff0c;有些格子必须放棋子#xff0c;剩下的格子随意。
要求放好棋子之后满足如下两条要求#xff1a; 第 i 行和第 i 列的棋子数目必须一样多。 第 i 行的棋子数…
文章目录题目描述解析代码题目描述
有一个n*n的棋盘可以在上面放棋子。 有些格子不能放棋子有些格子必须放棋子剩下的格子随意。
要求放好棋子之后满足如下两条要求 第 i 行和第 i 列的棋子数目必须一样多。 第 i 行的棋子数目不能超过总的棋子数目的 a/b。 求最多可以另外放多少个棋子除掉必须放的。如果无解输出 impossible。
解析
神仙题 这谁能想到是网络流啊… qwq 考虑正难则反考虑舍弃哪些棋子 对于一个可以放弃的棋子(i,j)(i,j)(i,j)就从 i 连一条向 j 流量1费用1的边。 然后对原点向每一行连一条流量是该行最多可以放置的棋子包括必放和选放 每列向汇点连同理的边 然后考虑放置棋子因为条件1的限制就从 i 行向 i 列连一条费用是0的边 这条边的流量就代表着第 i 行/列的放置的棋子数 这样就能使第i行和第i列选的棋子数相同 为了满足条件2暴力枚举这条边的最大容量判合法即可
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N105;
const int M2e6100;
const int mod998244353;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,s,t;
struct node{int to,nxt;ll cap,w;
}p[M1];
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;
queueintq;
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 flag0;while(!q.empty()){int nowq.front();q.pop();vis[now]0;for(int icur[now]fi[now];~i;ip[i].nxt){int top[i].to;if(!p[i].cap) continue;if(tot) flag1;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(xt||!lim){costlim*dis[t];return lim;}vis[x]1;ll res0;for(int icur[x];~i;ip[i].nxt){int top[i].to;if(vis[to]||!p[i].cap||dis[to]!dis[x]p[i].w) continue;ll adddfs(to,min(lim,p[i].cap));resadd;lim-add;p[i].cap-add;p[i^1].capadd;if(!lim) break;}if(lim) dis[x]-1;vis[x]0;return res;
}
void dinic(){flow0;cost0;while(spfa()){while(ll tmpdfs(s,2e18)){flowtmp;//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);s2*n1;ts1;tot0;res0;for(int i1;in;i){for(int j1;jn;j){if(mp[i][j]/) continue;heng[i];su[j];tot;if(mp[i][j].) addline(i,jn,1,1);else res;}}for(int i1;in;i){addline(s,i,heng[i],0);addline(in,t,su[i],0);addline(i,in,w,0);}dinic();
// printf(flow%d cost%d tot%d\n,flow,cost,tot);if(w*b(tot-cost)*aflowtot){flag1;ansmax(ans,tot-(int)cost);}
}
int main(){int o0;while(1){flag0;ans0;nread();aread();bread();if(nab0) break;for(int i1;in;i) scanf( %s,mp[i]1);for(int i0;in;i){work(i);}//work(1);o;printf(Case %d: ,o);if(!flag) printf(impossible\n);else printf(%d\n,ans-res);}return 0;
}
/**/
