给出一个n*n的网格,有些格子必须染成黑色,有些格子必须染成白色,其他格子可以染成黑色或者白色.要求最后第i行的黑格子数目等于第i列的黑格子数目,且某一行/列的格子数目不能超过格子总数的A/B. (把某个格子染黑等价于"在这个格子放一个芯片") n<=40
假设一共用了X个芯片(包括'C'和'.'两种情况下放的),那么每行每列最多放的芯片个数Y=X*A/B可以算出来.发现不同的Y值最多有40个,我们可以考虑枚举每个Y值,Y值确定之后X有一个下界,我们考虑此时最多放下的芯片个数能否达到这个下界即可. 建出2n个点分别代表n行n列,第i行向第j列连一条边. 如果(i,j)是'C',那么这条边的上下界均为1. 如果(i,j)是'.',那么这条边的上下界为[0,1] 如果(i,j)是'',那么上下界均为0(相当于没有边). 然后我们从第i列到第i行连一条下界为0上界为Y的边. 这张网络上一个满足流量平衡的流就对应一个合法的方案.我们要最大化代表格子的n*n条边里有流量的边数.不妨把这n*n条边的费用都设为1,我们现在只需要找出一个满足流量上下界限制且费用最大的循环流.接下来我的做法就纯属乱搞了,应该可以换成更加有理有据的上下界费用流 首先考虑满足流量上下界限制.套用上下界网络流中循环可行流那一套理论即可. 现在跑出来的可行流不一定是费用最大的,残量网络里可能有正权圈.所以...我们暴力跑spfa,每次增广一个残量网络上的正权圈,直到不存在正权圈,就找到了最大费用的可行流...(我也不知道这为什么是对的,求证明或证伪,不过它确实能过23333) 当然这个算法很慢,我们可以利用这张图的特性,手动消一些正权圈,细节看代码.我可能还需要学习一个有上下界的费用流
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int maxn=85,maxm=100005; struct edge{ int to,next,w,cost; }lst[maxm];int len=0,first[maxn],_first[maxn]; void addedge(int a,int b,int w,int cost){ lst[len].to=b;lst[len].next=first[a];lst[len].w=w;lst[len].cost=cost;first[a]=len++; lst[len].to=a;lst[len].next=first[b];lst[len].w=0;lst[len].cost=-cost;first[b]=len++; } int ans=0,maxans=-1; int totflow[maxn]; int pos[maxn][maxn]; void Add(int a,int b,int lo,int hi,int cost){ pos[a][b]=len; ans+=lo*cost;totflow[a]-=lo;totflow[b]+=lo; addedge(a,b,hi-lo,cost); } int n,A,B; char str[maxn][maxn]; int s,t,q[maxn],dis[maxn],vis[maxm],prt[maxn],fr[maxn],head,tail,T; bool bfs(){ head=tail=0;vis[s]=++T;dis[s]=1;q[tail++]=s; while(head!=tail){ int x=q[head++]; for(int pt=first[x];pt!=-1;pt=lst[pt].next){ if(lst[pt].w&&vis[lst[pt].to]!=T){ vis[lst[pt].to]=T;dis[lst[pt].to]=dis[x]+1;q[tail++]=lst[pt].to; } } } if(vis[t]==T)memcpy(_first,first,sizeof(first)); return vis[t]==T; } int dfs(int x,int lim){ if(x==t)return lim; int flow=0,a; for(int pt=_first[x];pt!=-1;pt=lst[pt].next){ _first[x]=pt; if(lst[pt].w&&dis[lst[pt].to]==dis[x]+1&&(a=dfs(lst[pt].to,min(lst[pt].w,lim-flow)))){ lst[pt].w-=a;lst[pt^1].w+=a;flow+=a;ans+=a*lst[pt].cost; if(flow==lim)return flow; } } return flow; } int dinic(){ int flow=0,x; while(bfs()){ while(x=dfs(s,0x3f3f3f3f)){ flow+=x; } } return flow; } void del(int x){ for(int pt=first[x];pt!=-1;pt=lst[pt].next)lst[pt].w=lst[pt^1].w=0; } bool inq[maxn]; int f[maxn]; bool spfa(){ for(int i=1;i<=2*n;++i)inq[i]=false; head=tail=0;++T; for(int i=1;i<=n;++i){ dis[i]=0;q[tail++]=i;vis[i]=T;inq[i]=true;prt[i]=-1; f[i]=1; } bool flag=false; while(head!=tail){ int x=q[head++];if(head==maxn)head=0;inq[x]=false; for(int pt=first[x];pt!=-1;pt=lst[pt].next){ if(f[x]>2*n){ flag=true;break; } if(lst[pt].w==0)continue;int y=lst[pt].to; if(vis[y]!=T||dis[y]<dis[x]+lst[pt].cost){ vis[y]=T; dis[y]=dis[x]+lst[pt].cost;f[y]=f[x]+1; prt[y]=pt; if(!inq[y]){ inq[y]=true;q[tail++]=y; if(tail==maxn)tail=0; } } } } if(flag){ for(int i=1;i<=2*n;++i){ if(f[i]>2*n){ vis[i]=++T; int pos=i; for(int pt=prt[i];vis[lst[pt^1].to]!=T;pt=prt[lst[pt^1].to]){ vis[lst[pt^1].to]=T;pos=lst[pt^1].to; } ++T; for(int pt=prt[pos];vis[pt]!=T;pt=prt[lst[pt^1].to]){ ans+=lst[pt].cost;lst[pt].w--;lst[pt^1].w++;vis[pt]=T; } break; } } return true; }else return false; } void addflow(int pt){ lst[pt].w--;lst[pt^1].w++;ans+=lst[pt].cost; } bool maxcost(){ int tmpsum=0; s=0;t=2*n+1; for(int i=1;i<=n*2;++i){ if(totflow[i]>0){ addedge(s,i,totflow[i],0); tmpsum+=totflow[i]; }else{ addedge(i,t,-totflow[i],0); } } if(dinic()!=tmpsum)return false; del(s);del(t); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(pos[i][n+j]==-1||pos[j][n+i]==-1||pos[n+i][i]==-1||pos[n+j][j]==-1)continue; if(i!=j&&lst[pos[i][n+j]].w&&lst[pos[j][n+i]].w&&lst[pos[n+i][i]].w&&lst[pos[n+j][j]].w){ addflow(pos[i][n+j]);addflow(pos[j][n+i]);addflow(pos[n+i][i]);addflow(pos[n+j][j]); } } } while(spfa()); return true; } bool check(int uplim){ ans=0;memset(first,-1,sizeof(first));len=0; memset(pos,-1,sizeof(pos)); for(int i=1;i<=n*2;++i)totflow[i]=0; for(int i=1;i<=n;++i)Add(n+i,i,0,uplim,0); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(str[i][j]=='C'){ Add(i,n+j,1,1,1); }else if(str[i][j]=='.'){ Add(i,n+j,0,1,1); } } } if(maxcost()){ int lim2=ceil(uplim/double(A)*double(B)); if(ans>=lim2&&ans>=maxans)maxans=ans; } } int main(){ int tests=0; while(scanf("%d%d%d",&n,&A,&B),n!=0){ maxans=-1;ans=0; ++tests; for(int i=1;i<=n;++i)scanf("%s",str[i]+1); int init=0,l=0,r=0; int sum=0; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(str[i][j]=='C'){ init++;sum++; }else if(str[i][j]=='.')sum++; } } if(1.0/n>A/double(B)){ if(init!=0)printf("Case %d: impossible\n",tests); else printf("Case %d: 0\n",tests); continue; } double bound=min((int)(sum*1.0*A/B),n); for(int uplim=bound;uplim>=0;--uplim){ check(uplim);if(maxans!=-1)break; } if(maxans!=-1)printf("Case %d: %d\n",tests,maxans-init); else printf("Case %d: impossible\n",tests); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7106225.html
相关资源：数据结构—成绩单生成器