题意:
见《挑战》P246.
直接套用模板即可：
//标号法，设立一个标号数组h[MAXN]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
#include<cstdio>
#include<vector>
using namespace std;const int MAXN = 510;
const int MAXM = 51010;
const int INF = 0x3f3f3f3f;struct Edge
{int from, to, cap, next, cost;
};Edge edge[MAXM];
int head[MAXN];
int h[MAXN];
int preve[MAXN];
int prevv[MAXN];
int dist[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int src, des, cnt;void addedge( int from, int to, int cap, int cost )
{edge[cnt].from = from;edge[cnt].to = to;edge[cnt].cap = cap;edge[cnt].cost = cost;edge[cnt].next = head[from];head[from] = cnt++;swap( from, to );edge[cnt].from = from;edge[cnt].to = to;edge[cnt].cap = 0;edge[cnt].cost = -cost;edge[cnt].next = head[from];head[from] = cnt++;
}int SPFA()
{deque<int> dq;int inqueue[MAXN];memset( dist, INF, sizeof dist );memset( inqueue, 0, sizeof inqueue );inqueue[src] = 1;dist[src] = 0;dq.push_back( src );while(!dq.empty()){int u = dq.front();dq.pop_front();inqueue[u] = 0;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(edge[i].cap&&dist[v] > dist[u] + edge[i].cost){dist[v] = dist[u] + edge[i].cost;prevv[v] = u;preve[v] = i;if(!inqueue[v]){if(!dq.empty() && dist[v] <= dist[dq.front()])dq.push_front( v );elsedq.push_back( v );}}}}return 0;
}int min_cost_flow(int f)
{memset( h, 0, sizeof h );int cost=0;while(f > 0){SPFA();if(dist[des] == INF)return -1;for(int i = 0; i < MAXN; i++)h[i] += dist[i];int d = f;for(int i = des; i != src; i = prevv[i]){d = min( d, edge[preve[i]].cap );}f -= d;cost += d*dist[des];for(int i = des; i != src; i = prevv[i]){edge[preve[i]].cap -= d;edge[preve[i] ^ 1].cap += d;}}return cost;
}int main()
{int n, k;src = 0;des = 505;int kase;cin >> kase;while(kase--){memset( head, -1, sizeof head );cnt = 0;cin >> n >> k;vector<int> x;for(int i = 1; i <= n; i++){cin >> a[i] >> b[i]>>c[i];x.push_back( a[i] );x.push_back( b[i] );}sort( x.begin(), x.end() );x.erase( unique( x.begin(), x.end() ), x.end() );//unique将重复元素放到最后并返回第一个重复元素的iteratorint m = x.size();int res = 0;addedge( src, 1, k, 0 );addedge( m, des, k, 0 );for(int i = 1; i < m; i++){addedge( i, i + 1, INF, 0 );}for(int i = 1; i <= n; i++){int u = find( x.begin(), x.end(), a[i] ) - x.begin();int v = find( x.begin(), x.end(), b[i] ) - x.begin();u++; v++;addedge( u, v, 1, -c[i] );//addedge( src, v, 1, 0 );//addedge( u, des, 1, 0 );//res += (-c[i]);}res = min_cost_flow( k );//res += min_cost_flow( k );cout << -res << endl;}return 0;
}