BZOJ 1061 志愿者招募

时间：2021-05-24 04:52:14

http://www.lydsy.com/JudgeOnline/problem.php?id=1061

思路:可以用不等式的改装变成费用流.

将不等式列出，如果有负的常数，那么就从等式连向T，如果是正的就从S连向等式，流量为常数，费用为0。

如果是变量，那么找出都有这个变量的两个等式，从负的连向正的流量为inf的边，如果有费用，那就再加上费用。

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #define inf 0x7fffffff

 int tot,go[],next[],first[],flow[],cost[];

 int op[],a[];

 int c[],vis[],dis[];

 int S,T,n,m,edge[],from[],ans;

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<='') {t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void insert(int x,int y,int z,int l){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     flow[tot]=z;

     cost[tot]=l;

 }

 void add(int x,int y,int z,int l){

     insert(x,y,z,l);op[tot]=tot+;

     insert(y,x,,-l);op[tot]=tot-;

 }

 bool spfa(){

     for (int i=S;i<=T;i++) vis[i]=,dis[i]=0x7fffffff;

     int h=,t=;vis[S]=;dis[S]=;

     while (h<=t){

         int now=c[h++];

         for (int i=first[now];i;i=next[i]){

               int pur=go[i];

               if (flow[i]&&dis[pur]>dis[now]+cost[i]){

                  edge[pur]=i;

                  from[pur]=now;

                  dis[pur]=dis[now]+cost[i];

                  if (vis[pur]) continue;

                  vis[pur]=;

                  c[++t]=pur;

                 }

         }

         vis[now]=;

     }

     return dis[T]!=0x7fffffff;

 }

 void updata(){

     int mn=0x7fffffff;

     for (int i=T;i!=S;i=from[i]){

        mn=std::min(mn,flow[edge[i]]);

     }

     for (int i=T;i!=S;i=from[i]){

       ans+=mn*cost[edge[i]];

       flow[edge[i]]-=mn;

       flow[op[edge[i]]]+=mn;

     }

 }

 int main(){

     n=read();m=read();

     S=;T=n+;

     for (int i=;i<=n;i++) a[i]=read();

     for (int i=;i<=m;i++){

          int u=read(),v=read(),c=read();

          add(u,v+,inf,c);

     }

     for (int i=;i<=n+;i++){

          int tmp=a[i]-a[i-];

          if (tmp>=) add(S,i,tmp,);

          else add(i,T,-tmp,);

          if (i>) add(i,i-,inf,);

     }

     while (spfa()) updata();

     printf("%d\n",ans);

 }

相关文章