题目描述 Description
"今天你要去远行，送你风雨中….."，伴着凄美的歌声，郭靖夫妇终于踏上征程。为了尽快到达边疆为国效力，他们搭上了2002次列车。可在途径sweet station时，被该站站长缠住了身，是什么原因呢？
因为该车站由于经营不善，面临破产，该站负责人早闻黄蓉聪明过人，一定要她帮忙出出主意，挽救车站。
该车站有n个车道，由于车道的长度有限，每个车道在某一时刻最多只能停靠一列火车。该站每天将有m列火车从车站经过，其中第i列火车到达车站的时间为Reach[i]，火车上装有价值Cost[i]的货物。
如果该火车进站，则车站将获得Cost[i]的1%收益，但由于货物的搬运时间，该火车将在车站停留一段时间Stay[i]，这段时间内，火车将占用车站中的某一个车道。当然，火车也可以不在站中停靠而直接出站，但这样车站将得不到一分钱。
要挽救车站，就是要对车站的列车进行调度，使获得的效益最大。当然，解决这个问题对于黄蓉来说并不难，但边疆吃紧，时间不等人，你能帮帮黄蓉，让她脱身吗？
任务:运行你的程序得到该站的最大效益。
输入描述 Input Description
第1行中为两个正整数：n（n≤20）m（m≤100），第2行到第m+1行，每行有3个不超过1000正整数。第i+1行的3个数分别为：Reach[i]， Cost[i]和Stay[i]，它们用单个空格分隔。
输出描述 Output Description
仅有一行，为车站的最大收益（精确到小数点后2位）。注意，如果火车a从第i车道离开时，火车b刚好到站（即Reach[a]+Stay[a] =Reach[b]），则它不能进入第i车道。
样例输入 Sample Input
1 3
2 5 1
3 4 1
5 6 2
样例输出 Sample Output
0.11
数据范围及提示 Data Size & Hint
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<sstream> #include<algorithm> #include<queue> #include<deque> #include<iomanip> #include<vector> #include<cmath> #include<map> #include<stack> #include<set> #include<functional> #include<memory> #include<list> #include<string> using namespace std; typedef long long LL; typedef unsigned long long ULL; /* 抽象到图： 找一系列首尾不相连的线段（最多n串），让这些线段的权值之和最大 最大费用最大流 将所有线段拆分为入点和出点，在入点和出点之间加边（容量为1，费用为cost[i]*0.01)，在不相邻的线段之间建边（容量为1，费用为0） 建立一个源点，向所有入点加边，容量为1，费用为0 建立一个汇点，所有出点向汇点加边，容量为1，费用为0 求出最大费用最大流 */ const int MAXN = 1000; const int MAXM = 10000; const int INF = 0x3f3f3f3f; struct Edge { int to, next, cap, flow; double cost; }edge[MAXM]; int head[MAXN], tol; int pre[MAXN]; double dis[MAXN]; int beg[MAXN], ed[MAXN]; double c[MAXN]; bool vis[MAXN]; int N;//节点总个数，节点编号从0~N-1 void init(int n) { N = n; tol = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v, int cap, double cost) { edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } bool spfa(int s, int t) { queue<int>q; for (int i = 0; i < N; i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if (!vis[v]) { vis[v] = true; q.push(v); } } } } //cout << dis[t] << endl; if (pre[t] == -1)return false; else return true; } //返回的是最大流，cost存的是最小费用 int minCostMaxflow(int s, int t, double &cost) { int flow = 0; cost = 0; while (spfa(s, t)) { int Min = INF; for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) { if (Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) { edge[i].flow += Min; edge[i ^ 1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow; } bool to[MAXN][MAXN]; int main() { //源点 为2*m + 2 汇点为2 * m + 1 ios::sync_with_stdio(0); int num, m; cin >> num >> m; init(2 * m + 3); for (int i = 1; i <= m; i++) { cin >> beg[i] >> c[i] >> ed[i]; ed[i] += beg[i]; c[i] *= 0.01; addedge(0, i, 1, 0); addedge(i + m, 2 * m + 1, 1, 0); addedge(i, i + m, 1, -c[i]); } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { if (j == i) continue; if (ed[i] < beg[j]) addedge(i + m, j, 1, 0); } } addedge(2 * m + 2, 0, num, 0); double ans; minCostMaxflow(2 * m + 2, 2 * m + 1, ans); printf("%.2lf ", -ans); }