【费用流】BZOJ1927-[Sdoi2010]星际竞速

【题目大意】

有一些点，它们之间存在一些有向边（由编号小的到编号大的），从一点到另一点消耗时间为边长。也可以消耗Ti时间直接抵达任意一个点。问所有点都走一遍最少需要多少时间？

【思路】

①将每个点i拆为i和i’。

②由S向i连(cap=1,cost=0)的边。由i'向T连(1,0)的边，表示抵达过该点。

③由S向i'连(1,Ti)的边，表示直接从某点跳转到i点。

④根据有向边[i，j]连(i,j')的边。

为什么这样是正确的？由于我们只关心每个点都被抵达过而不关心路径。费用流的前提是最大流，我们一定可以保证所有点都被经过，那么就可以通过③④区分是用跳转抵达还是通过有向边抵达了。

*好久不写费用流，华丽写挂一发。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define S 0

 #define T 2*n+1

 using namespace std;

 const int INF=0x7fffffff;

 const int MAXN=(+)*+;

 struct node

 {

     int to,pos,cap,cost;

 };

 int n,m;

 vector<node> E[MAXN];

 int pre[MAXN],preedge[MAXN];

 void addedge(int u,int v,int w,int cos)

 {

     E[u].push_back((node){v,E[v].size(),w,cos});

     E[v].push_back((node){u,E[u].size()-,,-cos});

 }

 void init()

 {

     scanf("%d%d",&n,&m);

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

     {

         int ai;

         scanf("%d",&ai);

         addedge(S,i+n,,ai);

         addedge(S,i,,);

         addedge(i+n,T,,);

     }

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

     {

         int ui,vi,wi;

         scanf("%d%d%d",&ui,&vi,&wi);

         if (ui>vi) swap(ui,vi);

         addedge(ui,vi+n,,wi);

     }

 }

 int spfa()

 {

     queue<int> que;

     int vis[MAXN],in[MAXN],dis[MAXN];

     memset(in,,sizeof(in));

     memset(pre,-,sizeof(pre));

     for (int i=S;i<=T;i++) dis[i]=INF;

     que.push(S);

     vis[S]=;

     dis[S]=;

     while (!que.empty())

     {

         int head=que.front();que.pop();

         vis[head]=;

         for (int i=;i<E[head].size();i++)

         {

             node &tmp=E[head][i];

             if (tmp.cap> && dis[tmp.to]>dis[head]+tmp.cost)

             {

                 dis[tmp.to]=dis[head]+tmp.cost;

                 pre[tmp.to]=head;

                 preedge[tmp.to]=i;

                 if (!in[tmp.to])

                 {

                     que.push(tmp.to);

                     in[tmp.to]=;

                 }

             }

         }

     }

     if (dis[T]==INF) return ;else return ;

     //和dinic不同，不能再tmp.to==T时直接返回，因为要找到最短路

 }

 void mcf()

 {

     int ans=;

     while (spfa())

     {

         int flow=INF;

         for (int i=T;pre[i]!=-;i=pre[i])

         {

             flow=min(flow,E[pre[i]][preedge[i]].cap);

         }

         for (int i=T;pre[i]!=-;i=pre[i])

         {

             node& tmp=E[pre[i]][preedge[i]];

             tmp.cap-=flow;

             E[tmp.to][tmp.pos].cap+=flow;

             ans+=flow*tmp.cost;

         }

     }

     printf("%d",ans);

 }

 int main()

 {

     init();

     mcf();

 }