<span id="b6cxw"></span>

^{<style id="b6cxw"></style>}

BZOJ 1497, 最大獲利

2019-11-11 03:17:09

字體：大中小

來源：轉載

供稿：網友

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;}

上一篇：jdbc往mysql讀取大文本文件

下一篇：BZOJ 1497, 最大獲利