附上题目链接：http://poj.org/problem?id=3680
题意大概是这样， 给你n个开区间， 每个开区间有一些权重， 现在从这些开区间里面选择一些区间， 使得每个点不被覆盖超过k次， 问你所能得到的最大权重是多少？ 题目分析见挑战p247, 这里我们附上另一份题解：
- /*
- 都说这题是构图很巧的好题~我也赞一个吧,虽然我没有想到。
- 说说我的思考过程吧。
- 做这题是因为这题在网络流的分类里面,自然一开始就想构图了~
- (1)能作为结点的东西的只有两个，区间和端点，区间没什么道理，以端点做结点的话，离散化是要的；
- (2)k限制流量用，段的权值与流量没什么关系，是一种费用性的东西，所以是费用流；
- (3)考虑到区间包含连续的点，我画了一个S->1->2->...->T的线图(流量限制为k，费用暂时为0)，并尝试对区间(a,b)(权值为w)加边add(S,a,w,1)和add(b,T,w,1)，但又捣乱了流量关系，于是继续凌乱中~
- 在哪个路口乱了咧？没理清楚的流量关系~差一点了！
- 建图改成代码中的那样后，即add(S,1,0,k)，add(cnt,T,0,k)，add(i,i+1,0,k)，add(a,b,-w,1)，a到b的流量一旦形成，a和b之间的点因为在a点之后，流量自然会超限，b之后的点流量也不会受影响，太可爱了！如果这个完整的思考过程属于我就爽了 代码如下：
-
#include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cstring> #include <iostream> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 450; struct Edge { int from, to, cap, flow, cost; }; vector<Edge> edges; vector<int> G[maxn]; int inque[maxn]; //spfa int d[maxn]; //源点到当前点的最短路 int p[maxn]; //入弧编号 int a[maxn]; //可改进量 void init(int n) { for(int i=0; i<=n; i++) G[i].clear(); edges.clear(); } void add_edge(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 m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool spfa(int s, int t, int &flow, long long &cost) { memset(d, 0x3f, sizeof(d)); memset(inque, 0, sizeof(inque)); d[s] = 0; inque[s] = 1; a[s] = inf; p[s] = 0; queue<int> que; que.push(s); while(!que.empty()){ int u = que.front(); que.pop(); inque[u] = 0; for(int i=0; i<G[u].size(); i++){ Edge e = edges[G[u][i]]; if(e.cap>e.flow && d[e.to]>d[u]+e.cost){ d[e.to] = d[u] + e.cost; if(!inque[e.to]) que.push(e.to), inque[e.to]=1; p[e.to] = G[u][i]; //e.to的入弧编号 a[e.to] = min(a[u], e.cap-e.flow); //更新可改进量 } } } if(d[t] == inf) return false; flow += a[t]; cost += (long long)a[t]*(long long)d[t]; for(int u=t; u!=s; u=edges[p[u]].from){ edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; } return true; } int MCMF(int s, int t, long long &cost) { int flow = 0; cost = 0; while(spfa(s, t, flow, cost)); return flow; } int aa[250], bb[250], ww[250]; vector<int> x; int main() { int T; scanf("%d", &T); while(T--) { int N, K; scanf("%d%d", &N, &K); x.clear(); for(int i=0; i<N; i++) { int a, b, w; scanf("%d%d%d", &a, &b, &w); x.push_back(a); x.push_back(b); aa[i] = a; bb[i] = b; ww[i] = w; } sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); //debug //for(int i=0; i<x.size(); i++) // cout<<x[i]<<' '; //cout<<endl; int m = x.size(); int s = m, t = m+1; init(m+1); add_edge(s, 0, K, 0); add_edge(m-1, t, K, 0); for(int i=0; i+1<x.size(); i++) { add_edge(i, i+1, K, 0); } for(int i=0; i<N; i++) { int u = find(x.begin(), x.end(), aa[i]) - x.begin(); int v = find(x.begin(), x.end(), bb[i]) - x.begin(); add_edge(u, v, 1, -ww[i]); } long long cost = 0; MCMF(s, t, cost); cout<<-cost<<endl; } return 0; }