簡(jiǎn)明題意：
給出一些開區(qū)間(s,e)以及權(quán)值c，要求選出一些區(qū)間，使得所有點(diǎn)的覆蓋次數(shù)小于k并且權(quán)值和最大。
解法：
對(duì)s
1,e
1,s
2,e
2..s
n,e
n進(jìn)行排序并去重，得到有序數(shù)列a
1,a
2,a
3..a
k，然后建立網(wǎng)絡(luò)，在a
i與a
i+1之間連一條容量為k，費(fèi)用為0的邊，對(duì)于原有區(qū)間(s,e)，在s',e'（s',e'指離散化后的值）之間連一條容量為1，費(fèi)用為-c的邊，然后建立源點(diǎn)，向a
1連一條容量為k，費(fèi)用為0的邊；建立匯點(diǎn)，從a
k向其連容量為k，費(fèi)用為0的邊，最后求最小費(fèi)用流即可
代碼：
1
# include <cstdio>
2# include <vector>
3# include <cstring>
4# include <algorithm>
5using namespace std;
6# define N 500 //N+2
7# define E 10000 //2*E
8#define typef int // type of flow
9#define typec int // type of cost
10const int inff = 0xfffffff; // max of flow
11const int infc = 0xfffffff; // max of cost
12struct network
13
{
14
int nv, ne, pnt[E], nxt[E];
15 int vis[N], que[N], head[N], pv[N], pe[N];
16 typef flow, cap[E]; typec cost, dis[E], d[N];
17 void addedge(int u, int v, typef c, typec w)
18
{
19 pnt[ne] = v; cap[ne] = c;
20 dis[ne] = +w; nxt[ne] = head[u]; head[u] = (ne++);
21 pnt[ne] = u; cap[ne] = 0;
22 dis[ne] = -w; nxt[ne] = head[v]; head[v] = (ne++);
23
}
24 int mincost(int src, int sink)
25 {
26 int i, k, f, r; typef mxf;
27 for (flow = 0, cost = 0; ; )
28 {
29 for(i=0;i<nv;i++) pv[i]=-1,d[i] = infc;
30 memset(vis, 0, sizeof(vis));
31 d[src] = 0; pv[src] = src; vis[src] = 1;
32 for (f = 0, r = 1, que[0] = src; r != f; )
33 {
34 i = que[f++]; vis[i] = 0;
35 if (N == f) f = 0;
36 for (k = head[i]; k != -1; k = nxt[k])
37 if(cap[k] && dis[k]+d[i] < d[pnt[k]])
38 {
39 d[pnt[k]] = dis[k] + d[i];
40 if (0 == vis[pnt[k]])
41 {
42 vis[pnt[k]] = 1;
43 que[r++] = pnt[k];
44 if (N == r) r = 0;
45 }
46 pv[pnt[k]]=i; pe[pnt[k]]=k;
47 }
48 }
49 if (-1 == pv[sink]) break;
50 for (k = sink, mxf = inff; k != src; k = pv[k])
51 if (cap[pe[k]] < mxf) mxf = cap[pe[k]];
52 flow += mxf; cost += d[sink] * mxf;
53 for (k = sink; k != src; k = pv[k])
54 {
55 cap[pe[k]] -= mxf; cap[pe[k] ^ 1] += mxf;
56 }
57 }
58 return cost;
59 }
60 void build(int v)
61 {
62 nv = v; ne = 0;
63 for(int i=0;i<v;i++)
64 head[i]=-1;
65 }
66 void add(int x,int y,int f,int w)//x->y up=f,cost=w
67 {
68 addedge(x, y, f, w);
69 }
70
} net;
71int data[400][3];
72vector<int> map;
73int main()
74{
75 int test;
76 scanf("%d",&test);
77 while(test--)
78 {
79 map.clear();
80 int n,k;
81 scanf("%d%d",&n,&k);
82 for(int i=0;i<n;i++)
83 {
84 scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
85 map.push_back(data[i][0]);
86 map.push_back(data[i][1]);
87 }
88 sort(map.begin(),map.end());
89 vector<int>::iterator end=unique(map.begin(),map.end());
90 while(map.end()!=end) map.pop_back();
91 net.build(map.size()+2);
92 for(int i=0;i<map.size()+1;i++)
93 net.add(i,i+1,k,0);
94 for(int i=0;i<n;i++)
95 net.add(lower_bound(map.begin(),map.end(),data[i][0])-map.begin()+1,lower_bound(map.begin(),map.end(),data[i][1])-map.begin()+1,1,-data[i][2]);
96 printf("%d\n",-net.mincost(0,map.size()+1));
97 }
98 return 0;
99}
100