构图参考：http://www.cppblog.com/abilitytao/archive/2010/03/30/111042.html
1 // File Name: 3680.cpp 2 // Author: Missa 3 // Created Time: 2013/4/19 星期五 15:57:48 4 5 #include<iostream> 6 #include<cstdio> 7 #include<cstring> 8 #include<algorithm> 9 #include<cmath> 10 #include<queue> 11 #include<stack> 12 #include<string> 13 #include<vector> 14 #include<cstdlib> 15 #include<map> 16 #include<set> 17 using namespace std; 18 #define CL(x,v) memset(x,v,sizeof(x)); 19 #define R(i,st,en) for(int i=st;i<en;++i) 20 #define LL long long 21 22 const int maxn = 450; 23 const int maxm = 450 * 450; 24 const int inf = 0x3f3f3f3f; 25 struct Edge 26 { 27 int v, cap, cost, next; 28 }p[maxm << 1]; 29 int e, sumFlow, n, m, st, en; 30 int head[maxn], dis[maxn], pre[maxn]; 31 bool vis[maxn]; 32 void init() 33 { 34 e=0; 35 memset(head,-1,sizeof(head)); 36 } 37 void addEdge(int u,int v,int cap,int cost) 38 { 39 p[e].v = v; p[e].cap = cap; p[e].cost = cost; 40 p[e].next = head[u]; head[u] = e++; 41 p[e].v = u; p[e].cap = 0; p[e].cost = - cost; 42 p[e].next = head[v]; head[v] = e++; 43 } 44 bool spfa(int s,int t, int n) 45 { 46 int u,v; 47 queue<int>q; 48 memset(vis,false,sizeof(vis)); 49 memset(pre,-1,sizeof(pre)); 50 for(int i = 0; i <= n; ++i) 51 dis[i] = inf; 52 vis[s] = true; 53 dis[s] = 0; 54 q.push(s); 55 while(!q.empty()) 56 { 57 u = q.front(); 58 q.pop(); 59 vis[u] = false; 60 for(int i = head[u]; i != -1; i = p[i].next) 61 { 62 v = p[i].v; 63 if(p[i].cap && dis[v] > dis[u] + p[i].cost) 64 { 65 dis[v] = dis[u] + p[i].cost; 66 pre[v] = i; 67 if(!vis[v]) 68 { 69 q.push(v); 70 vis[v]=true; 71 } 72 } 73 } 74 } 75 if(dis[t] == inf) 76 return false; 77 return true; 78 } 79 int MCMF(int s,int t,int n) 80 { 81 int flow = 0; // 总流量 82 int minflow, mincost; 83 mincost=0; 84 while(spfa(s,t,n)) 85 { 86 minflow = inf + 1; 87 for(int i = pre[t]; i != -1; i = pre[p[i^1].v]) 88 if(p[i].cap < minflow) 89 minflow = p[i].cap; 90 flow += minflow; 91 for(int i=pre[t];i!=-1;i=pre[p[i^1].v]) 92 { 93 p[i].cap -= minflow; 94 p[i^1].cap += minflow; 95 } 96 mincost += dis[t] * minflow; 97 } 98 sumFlow = flow; // 最大流 99 return mincost; 100 } 101 int N, K; 102 struct Node 103 { 104 int u, v, c; 105 }ed[maxn]; 106 int pos[100005]; 107 vector<int>v; 108 int main() 109 { 110 int test; 111 scanf("%d",&test); 112 while (test--) 113 { 114 init(); 115 n = 1; 116 memset(pos, 0, sizeof(pos)); 117 scanf("%d%d", &N, &K); 118 v.clear(); 119 for (int i = 0; i < N; ++i) 120 { 121 scanf("%d%d%d",&ed[i].u, &ed[i].v, &ed[i].c); 122 v.push_back(ed[i].u); 123 v.push_back(ed[i].v); 124 } 125 sort(v.begin(),v.end()); 126 for (int i = 0; i < v.size(); ++i) 127 if (pos[v[i]] == 0) 128 pos[v[i]] = n ++; 129 st = 0, en = n; 130 for (int i = 0; i < n; ++i) 131 addEdge(i, i + 1, K, 0); 132 for (int i = 0; i < N; ++i) 133 addEdge(pos[ed[i].u], pos[ed[i].v], 1, -ed[i].c); 134 printf("%d\n",-MCMF(st, en, n)); 135 } 136 return 0; 137 }