题目大意就是给m个火车的到达时间、停留时间和车载货物的价值，车站有n个车道，而火车停留一次车站就会从车载货物价值中获得1%的利润，让你来求一种安排方法，使得车站收益最大，并输出收益值。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <queue>
7 using namespace std;
8 const int INF = 10000000;
9 const int maxe = 10000;
10 const int maxn = 500;
11 int n,m,reach[maxn],stay[maxn],cost[maxn],vis[maxn<<1],d[maxn<<1],h[maxn<<1],pre[maxn<<1],rid[maxn],cid[maxn],now;
12 double ans;
13 struct edge{
14 int to,cost,cap,next;
15 }tr[maxe];
16 inline void init(){
17 now = 0;
18 memset(h,-1,sizeof(h));
19 memset(tr,0,sizeof(tr));
20 memset(reach,0,sizeof(reach));
21 memset(stay,0,sizeof(stay));
22 memset(cost,0,sizeof(cost));
23 }
24 inline void add(int u,int v,int cap,int cost){
25 tr[now].to = v;tr[now].cap = cap;tr[now].cost = cost;tr[now].next = h[u];
26 h[u] = now++;
27 tr[now].to = u;tr[now].cap = 0;tr[now].cost = -cost;tr[now].next = h[v];
28 h[v] = now++;
29 }
30 bool SPFA(int s,int t,int &flow,int &cost){
31 for(int i = s;i <= t;++i){
32 d[i] = INF;
33 }
34 int minflow = INF;
35 memset(vis,0,sizeof(vis));
36 memset(pre,-1,sizeof(pre));
37 deque<int>q;
38 d[s] = 0;
39 vis[s] = 1;
40 q.push_back(s);
41 while(!q.empty()){
42 int x = q.front();q.pop_front();
43 vis[x] = 0;
44 for(int i = h[x];i != -1;i = tr[i].next){
45 edge e = tr[i];
46 if(d[e.to] > d[x] + e.cost && e.cap){
47 d[e.to] = d[x] + e.cost;
48 pre[e.to] = i;
49 minflow = min(minflow,e.cap);
50 if(!vis[e.to]){
51 vis[e.to] = 1;
52 q.push_back(e.to);
53 }
54 }
55 }
56 }
57 if(d[t] == INF)return false;
58 flow += minflow;
59 cost += d[t] * minflow;
60 for(int i = t;i != s;i = tr[pre[i]^1].to){
61 tr[pre[i]].cap -= minflow;
62 tr[pre[i]^1].cap += minflow;
63 }
64 return true;
65 }
66 int MCMF(int s,int t){
67 int flow = 0,cost = 0;
68 while(SPFA(s,t,flow,cost));
69 return cost;
70 }
71 int main(){
72 scanf("%d%d",&n,&m);
73 init();
74 for(int i = 1;i <= m;++i){
75 scanf("%d%d%d",&reach[i],&cost[i],&stay[i]);
76 rid[i] = 2*i;cid[i] = 2*i-1;
77 add(cid[i],rid[i],1,-cost[i]);
78 }
79 for(int i = 1;i <= m;++i){
80 for(int j = 1;j <= m;++j){
81 if(j != i)
82 if(reach[i] + stay[i] < reach[j]){
83 add(rid[i],cid[j],1,0);
84 }
85 }
86 }
87 int S = 0,T = 2*m+1,ST = 2*m+2;
88 for(int i = 1;i <= m;++i){
89 add(S,cid[i],1,0);
90 }
91 for(int i = 1;i <= m;++i){
92 add(rid[i],T,1,0);
93 }
94 add(T,ST,n,0);
95 ans = double(MCMF(S,ST))/100;
96 printf("%0.2lf\n",-ans);
97 return 0;
98 }