【费用流】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')的边。

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

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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue>
  7 #define S 0
  8 #define T 2*n+1
  9 using namespace std;
 10 const int INF=0x7fffffff;
 11 const int MAXN=(800+50)*2+1;
 12 struct node
 13 {
 14     int to,pos,cap,cost;
 15 };
 16 int n,m;
 17 vector<node> E[MAXN];
 18 int pre[MAXN],preedge[MAXN];
 19 
 20 void addedge(int u,int v,int w,int cos)
 21 {
 22     E[u].push_back((node){v,E[v].size(),w,cos});
 23     E[v].push_back((node){u,E[u].size()-1,0,-cos});
 24 }
 25 
 26 void init()
 27 {
 28     scanf("%d%d",&n,&m);
 29     for (int i=1;i<=n;i++)
 30     {
 31         int ai;
 32         scanf("%d",&ai);
 33         addedge(S,i+n,1,ai);
 34         addedge(S,i,1,0);
 35         addedge(i+n,T,1,0);
 36     }
 37     for (int i=0;i<m;i++)
 38     {
 39         int ui,vi,wi;
 40         scanf("%d%d%d",&ui,&vi,&wi);
 41         if (ui>vi) swap(ui,vi);
 42         addedge(ui,vi+n,1,wi);
 43     }
 44 }
 45 
 46 int spfa()
 47 {
 48     queue<int> que;
 49     int vis[MAXN],in[MAXN],dis[MAXN];
 50     memset(in,0,sizeof(in));
 51     memset(pre,-1,sizeof(pre));
 52     for (int i=S;i<=T;i++) dis[i]=INF;
 53     que.push(S);
 54     vis[S]=1;
 55     dis[S]=0;
 56     while (!que.empty())
 57     {
 58         int head=que.front();que.pop();
 59         vis[head]=0;
 60         for (int i=0;i<E[head].size();i++)
 61         {
 62             node &tmp=E[head][i];
 63             if (tmp.cap>0 && dis[tmp.to]>dis[head]+tmp.cost)
 64             {
 65                 dis[tmp.to]=dis[head]+tmp.cost;
 66                 pre[tmp.to]=head;
 67                 preedge[tmp.to]=i;
 68                 if (!in[tmp.to])
 69                 {
 70                     que.push(tmp.to);
 71                     in[tmp.to]=0;
 72                 }
 73             }
 74         }
 75     }
 76     if (dis[T]==INF) return 0;else return 1;
 77     //和dinic不同，不能再tmp.to==T时直接返回，因为要找到最短路 
 78 } 
 79 
 80 void mcf()
 81 {
 82     int ans=0;
 83     while (spfa())
 84     {
 85         int flow=INF; 
 86         for (int i=T;pre[i]!=-1;i=pre[i])
 87         {
 88             flow=min(flow,E[pre[i]][preedge[i]].cap);
 89         }
 90         for (int i=T;pre[i]!=-1;i=pre[i])
 91         {
 92             node& tmp=E[pre[i]][preedge[i]];
 93             tmp.cap-=flow;
 94             E[tmp.to][tmp.pos].cap+=flow;
 95             ans+=flow*tmp.cost;
 96         }
 97     }
 98     printf("%d",ans);
 99 }
100 
101 int main()
102 {
103     init();
104     mcf();
105 }