BZOJ 1927 星际竞速

时间：2021-02-19 15:44:52

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

思路:把一个点拆成两个点，

S->i 费用0，流量1 (代表这个点可以移动到其他点所必备的流量)

i+n->T 费用0，流量1 (每个点都必须要走过)

u->v+n 费用w,流量1  (代表可以移动到那个点)

S->i+n 费用a[i],流量1 (代表从这个点瞬移)

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

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

 int op[],dis[],c[],vis[],edge[],from[];

 int S,T,n,m,ans;

 int read(){

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

     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++)

      dis[i]=0x3f3f3f3f,vis[i]=;

     int h=,t=;c[]=S;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 (dis[pur]>dis[now]+cost[i]&&flow[i]){

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

                 edge[pur]=i;

                 from[pur]=now;

                 if (vis[pur]) continue;

                 vis[pur]=;

                 c[++t]=pur;

             }

         }

         vis[now]=;

     }

     return dis[T]!=0x3f3f3f3f;

 }

 void updata(){

     int mn=0x7ffffff;

     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+n+;

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

      add(S,i,,);

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

         int x=read();

         add(S,i+n,,x);

     }

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

         add(i+n,T,,);

     while (m--){

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

         if (u>v) std::swap(u,v);

         add(u,v+n,,w);

     }

     ans=;

     while (spfa()) updata();

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

 }

相关文章