本文共 2570 字，大约阅读时间需要 8 分钟。
题意:
见《挑战》P246.
直接套用模板即可：
//标号法，设立一个标号数组h[MAXN]#include#include #include #include #include #include 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 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 ); else dq.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 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将重复元素放到最后并返回第一个重复元素的iterator int 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;}
转载地址：http://puyci.baihongyu.com/