习题：codevs 1035 火车停留解题报告

本蒟蒻又来写解题报告了。这次的题目是codevs 1035 火车停留。

题目大意就是给m个火车的到达时间、停留时间和车载货物的价值，车站有n个车道，而火车停留一次车站就会从车载货物价值中获得1%的利润，让你来求一种安排方法，使得车站收益最大，并输出收益值。

蒟蒻的思路是这样的：

一眼看出：最大费用最大流（MCMF）
显然cost:表示车站收益
然后……
以车站为点建立图求流？同一个车站可能经过好几辆火车……，貌似很麻烦……；
那么以什么建图、连边，还有怎么连？
貌似有点类似于方格取数2之中的拆点……；
那么这个就可以……以火车为点，把一个点拆成两个，然后建立流的关系。
Reach[i]和stay[i]作为建立不同火车是否可以建边的判断条件
假设火车i，将其分为点2*i-1和2*i，连一条流量为1，费用为-cost[i]的边
如果reach[i] + stay[i] < reach[j]，在2*i和2*j-1之间连一条流量为1，费用为0的边。
建立汇点和起点S,T，从S向每个2*i-1连一条流量为1，费用为0的边。从每个2*i向T连一条流量为1，费用为0的边。

那么怎么限制n个车道呢？其实很简单，只需要建立超级汇点ST，然后从T向ST连一条流量为n，费用为0的边。

这样这个题目就大功告成了，代码不长，刚98行。建议大家还是去刷一下代码能力题，因为NOIP2015蒟蒻就被代码能力题给坑惨了。

废话不多说，上代码

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <algorithm>
 #include <queue>
 using namespace std;
 const int INF = ;
 const int maxe = ;
 const int maxn = ;
 int n,m,reach[maxn],stay[maxn],cost[maxn],vis[maxn<<],d[maxn<<],h[maxn<<],pre[maxn<<],rid[maxn],cid[maxn],now;
 double ans;
 struct edge{
     int to,cost,cap,next;
 }tr[maxe];
 inline void init(){
     now = ;
     memset(h,-,sizeof(h));
     memset(tr,,sizeof(tr));
     memset(reach,,sizeof(reach));
     memset(stay,,sizeof(stay));
     memset(cost,,sizeof(cost));
 }
 inline void add(int u,int v,int cap,int cost){
     tr[now].to = v;tr[now].cap = cap;tr[now].cost = cost;tr[now].next = h[u];
     h[u] = now++;
     tr[now].to = u;tr[now].cap = ;tr[now].cost = -cost;tr[now].next = h[v];
     h[v] = now++;
 }
 bool SPFA(int s,int t,int &flow,int &cost){
     for(int i = s;i <= t;++i){
         d[i] = INF;
     }
     int minflow = INF;
     memset(vis,,sizeof(vis));
     memset(pre,-,sizeof(pre));
     deque<int>q;
     d[s] = ;
     vis[s] = ;
     q.push_back(s);
     while(!q.empty()){
         int x = q.front();q.pop_front();
         vis[x] = ;
         for(int i = h[x];i != -;i = tr[i].next){
             edge e = tr[i];
             if(d[e.to] > d[x] + e.cost && e.cap){
                 d[e.to] = d[x] + e.cost;
                 pre[e.to] = i;
                 minflow = min(minflow,e.cap);
                 if(!vis[e.to]){
                     vis[e.to] = ;
                     q.push_back(e.to);
                 }
             }
         }
     }
     if(d[t] == INF)return false;
     flow += minflow;
     cost += d[t] * minflow;
     for(int i = t;i != s;i = tr[pre[i]^].to){
         tr[pre[i]].cap -= minflow;
         tr[pre[i]^].cap += minflow;
     }
     return true;
 }
 int MCMF(int s,int t){
     int flow = ,cost = ;
     while(SPFA(s,t,flow,cost));
     return cost;
 }
 int main(){
     scanf("%d%d",&n,&m);
     init();
     for(int i = ;i <= m;++i){
         scanf("%d%d%d",&reach[i],&cost[i],&stay[i]);
         rid[i] = *i;cid[i] = *i-;
         add(cid[i],rid[i],,-cost[i]);
     }
     for(int i = ;i <= m;++i){
         for(int j = ;j <= m;++j){
             if(j != i)
                 if(reach[i] + stay[i] < reach[j]){
                     add(rid[i],cid[j],,);
                 }
         }
     }
     int S = ,T = *m+,ST = *m+;
     for(int i = ;i <= m;++i){
         add(S,cid[i],,);
     }
     for(int i = ;i <= m;++i){
         add(rid[i],T,,);
     }
     add(T,ST,n,);
     ans = double(MCMF(S,ST))/;
     printf("%0.2lf\n",-ans);
     return ;
 }

如果大家认为有用的话，欢迎转载。如果大家有意见的话，请在下方评论栏中给我留言，或者给我的E-mail [e-mail]发邮件留言。谢谢大家。