本蒟蒻又来写解题报告了。这次的题目是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 PC-worker@outlook.com发邮件留言。谢谢大家。