BZOJ 1497, 最大获利

2019-11-11 04:52:41

字体：大中小

来源：转载

供稿：网友

PRoblem

传送门

Mean

选择合理方案新建基站，满足部分用户群需要，求最大获利（净获利 = 获益之和 - 投入成本之和）。

Analysis

注意到类似于有向无环图的性质，套用最小割模型中的最大权闭合图即可。

参考资料：胡伯涛2007年集训队论文《最小割模型在信息学竞赛中的应用》

Code

#include<cstdio>#include<cstring>const int INF=~0U>>2,V=55005,E=320005;int n,m,s,t,x,y,z,l,r,sum,ans,ed=1,u[E],v[E],c[E],nxt[E],g[V],cur[V],vis[V],q[V],d[V];int min(int a,int b){return a<b?a:b;}void read(int &x){ char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}void add(int x,int y,int z){ u[++ed]=x,v[ed]=y,c[ed]=z,nxt[ed]=g[x],g[x]=ed; u[++ed]=y,v[ed]=x,c[ed]=0,nxt[ed]=g[y],g[y]=ed;}bool bfs(){ memset(vis,0,sizeof(vis)); vis[l=r=0]=1; while(l<=r){ int x=q[l++]; for(int i=g[x];i;i=nxt[i]) if(!vis[v[i]] && c[i]){ vis[v[i]]=1; d[v[i]]=d[x]+1; q[++r]=v[i]; } } return vis[t];}int dfs(int x,int a){ if(x==t || !a) return a; int flow=0,f; for(int &i=cur[x];i;i=nxt[i]){ if(d[x]+1==d[v[i]] && (f=dfs(v[i],min(a,c[i])))>0){ c[i]-=f; c[i^1]+=f; flow+=f; a-=f; if(!a) break; } } return flow;}int main(){ read(n),read(m); t=n+m+1; for(int i=1;i<=n;i++){ read(x); add(i,t,x); } for(int i=1;i<=m;i++){ int now=i+n; read(x),read(y),read(z); add(now,x,INF),add(now,y,INF); add(0,now,z); sum+=z; } while(bfs()){ for(int i=0;i<=t;i++) cur[i]=g[i]; ans+=dfs(s,INF); } printf("%d",sum-ans); return 0;}

上一篇：mysql中整型细分

下一篇：深入理解JVM内幕