目录

BZOJ1497 最大获利

题解

比较容易想到的一道网络流。从源点向每一个中转站连一条流量为\(Pi\)的边，从每个中转站向其对应的消费人群连一条流量为\(inf\)的边，从每个消费人群向汇点连一条流量为\(Ci\)的边。然后就转化成了最小割的问题了。由于中间消费人群与中转站的边流量是\(inf\)，所以是不会割这条边的。而割左右两边的边就代表放弃这种方案，最后用\(\sum_{i=1}^n z[i]\)减去最小割的值就是最大的获利了。

ｃｏｄｅ

#include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/const int maxn=1e5+500;const int inf=1e9+7;#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);int n,m,tot=1;struct edge {    int to,nxt,v;}E[maxn<<2];int head[maxn],dis[maxn];int S,T;/*==================Define Area================*/void addedge(int u,int v,int w) {    E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[tot].v=w;    E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot;E[tot].v=0;}bool bfs() {    memset(dis,-1,sizeof dis);    queue
         
          Q; while(!Q.empty()) Q.pop(); Q.push(S); dis[S]=0; while(!Q.empty()) { int o=Q.front();Q.pop(); for(int i=head[o];~i;i=E[i].nxt) { int to=E[i].to; if(dis[to]==-1&&E[i].v) { dis[to]=dis[o]+1; Q.push(to); } } } return dis[T]!=-1; }int dfs(int u,int flow) { if(u==T) return flow; int used=0,k; for(int i=head[u];~i;i=E[i].nxt) { int to=E[i].to; if(dis[to]==dis[u]+1&&E[i].v) { k=dfs(to,min(E[i].v,flow-used)); E[i].v-=k; E[i^1].v+=k; used+=k; if(used==flow) return flow; } } if(!used) dis[u]=-1; return used;}int main() { memset(head,-1,sizeof head); read(n);read(m); S=0,T=n+m+1; for(int i=1,x;i<=n;i++) { read(x); addedge(S,i,x); } int ans=0; for(int i=1,x,y,z;i<=m;i++) { read(x);read(y);read(z); addedge(x,n+i,inf);addedge(y,n+i,inf); addedge(n+i,T,z); ans+=z; } while(bfs()) { ans-=dfs(S,inf); } printf("%d\n",ans); return 0; }