本文主要是介绍火车停留 wiki 1035，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先这题N和M都很小，可以往网络流方面想。
怎么用网络流搞呢，其实就是按题目描述搞，cost显然就是费用，而每个站台同一时间只能停一辆车，以及总站台数的限制显然就是流量，想到这里基本上脑子里已经有一个大概的模型了。
1.肯定要拆点，因为涉及到时间，不拆点不能处理时间的前后关系。
2.拆点肯定是按火车拆，因为火车可以随意选择剩下的车站，以车站为点显然不方便。
以上两点想到之后这题就基本解决了，可以着手建图了。
1.对于火车 i ，拆成两个点，i 和 i’ ，i 向 i‘ 连一条容量为1，费用为cost[i]的边，表示这辆火车进站停留。
2.建立一个源点S，从S向每个i 连一条容量为1，费用为0的边，表示这辆车为第一个进入车站停留的（由于语文不好，这里可能有点表意不清，大家稍微想一想应该就懂了）
3.建立一个汇点T，从每个i’ 向T连一条容量为1，费用为0的边，表示这辆车为最后一个出站的（同上）
4.建立一个超级汇点ST，从T向ST连一条容量为n，费用为0的边，用来限制n个车站
5.对于每个i和j，若满足reach[i]+stay[i]<reach[j],就从i‘ 向 j 连一条容量为1，费用为0的边，表示i出站之后，j可以进同一个站
整个建图过程直观清晰。
然后做S到ST的最大费用最大流就可以了
TIPS：1.最大费用最大流可以将边的费用取反，之后用最小费用流的SPFA做，答案取反就可以了。
2.答案别忘了除以100
我的AC代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
#define INT_MAX 0x07777777
struct Edge {int from, to, cap, flow, cost;
};
int n,m,sz,s,t,result;
vector<Edge> edges;
vector<int> G[300];
int inq[300],a[300],d[300],reach[300],cost[300],stay[300],node[300],p[300];
void add(int from, int to, int cap, int cost){edges.push_back(Edge{from,to,cap,0,cost});edges.push_back(Edge{to,from,0,0,-cost});int count = edges.size();G[from].push_back(count-2);G[to].push_back(count-1);
}
void init(){scanf("%d%d", &n,&m);for(int i = 0; i < m; i++){scanf("%d%d%d", &reach[i], &cost[i], &stay[i]);cost[i] = -cost[i];}add(0, 1, n, 0);sz = 2;for(int i = 0; i < m; i++){node[i] = sz;add(1, sz, 1, 0);sz++;add(sz-1,sz,1,cost[i]);sz++;}for(int i = 0; i < m; i++){add(node[i]+1, sz, 1, 0);}sz++;t = sz-1;for(int i = 0; i < m; i++){for(int j = 0; j < m; j++){if(i!=j && reach[i]+stay[i]<reach[j]){add(node[i]+1, node[j], 1, 0);}}}
}
void solve(){result = 0;memset(a, 0, sizeof(a));a[0] = INT_MAX;while (true) {memset(inq, 0, sizeof(inq));inq[0] = 1;for(int i = 0; i < 300; i++) d[i] = INT_MAX;d[0] = 0;queue<int> q;q.push(0);while (!q.empty()) {int u = q.front();q.pop();inq[u] = 0;for(int i = 0; i < G[u].size(); i++){Edge& e = edges[G[u][i]];if (d[e.to] > d[e.from]+e.cost && e.cap > e.flow) {d[e.to] = d[e.from]+e.cost;a[e.to] = (a[u] < e.cap-e.flow ? a[u] : e.cap-e.flow);p[e.to] = G[u][i];if(!inq[e.to]) {q.push(e.to); inq[e.to] = 1;}}}}if (d[t]==INT_MAX) break;int u = t;while (u) {edges[p[u]].flow += a[t];edges[p[u]^1].flow -= a[t];u = edges[p[u]].from;}result += a[t]*d[t];}printf("%.2f\n", -(((double)result))/100);
}
int main(int argc, const char * argv[])
{init();solve();
}
这篇关于火车停留 wiki 1035的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
