本蒟蒻又來寫解題報告了。這次的題目是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蒟蒻就被代碼能力題給坑慘了。
廢話不多說，上代碼
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 }
如果大家認為有用的話，歡迎轉載。如果大家有意見的話，請在下方評論欄中給我留言，或者給我的E-mail [email protected]發郵件留言。謝謝大家。
