通过区间图最大权独立集的状态转移方程可以推断出建图方法，然后跑最小费用流，这里用了满流法来处理负权问题，说实在作为挑战程序设计网络流章最后一个题还是有一定难度的，至少我看了题解以后还似懂非懂，等我再接触一些网络流后会回来重新做这个题
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 510; const int INF = 0x3f3f3f3f; //========================= typedef pair<int, int> P; struct Edge { int to, cap, cost, rev; Edge(int a, int b, int c, int d) : to(a), cap(b), cost(c), rev(d) {} }; int V; vector<Edge> G[maxn]; int h[maxn]; int dist[maxn]; int prevv[maxn], preve[maxn]; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int u, int v, int cap, int cost) { G[u].push_back(Edge(v, cap, cost, G[v].size())); G[v].push_back(Edge(u, 0, -cost, G[u].size()-1)); } int min_cost_flow(int s, int t, int f) { int res = 0; memset(h, 0, sizeof(h)); while (f > 0) { priority_queue<P, vector<P>, greater<P> > q; memset(dist, INF, sizeof(dist)); dist[s] = 0; q.push(P(0, s)); while (!q.empty()) { P p = q.top(); q.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; q.push(P(dist[e.to], e.to)); } } } if (dist[t] == INF) return -1; for (int v = 0; v < V; v++) h[v] += dist[v]; int d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d*h[t]; for (int v = t; v != s; v = prevv[v]) { Edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } //========================== int T, n, k; int a[maxn], b[maxn], w[maxn]; void solve() { vector<int> x; for (int i = 0; i < n; 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()); int m = x.size(); int s = m, t = m + 1; V = t + 1; int ans = 0; addedge(s, 0, k, 0); addedge(m-1, t, k, 0); for (int i = 0; i < m - 1; i++) { addedge(i, i + 1, INF, 0); } for (int i = 0; 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(); addedge(v, u, 1, w[i]); addedge(s, v, 1, 0); addedge(u, t, 1, 0); ans -= w[i]; } ans += min_cost_flow(s, t, k+n); printf("%d\n", -ans); } int main() { scanf("%d", &T); while (T--) { scanf("%d %d", &n, &k); init(); for (int i = 0; i < n; i++) { scanf("%d %d %d", &a[i], &b[i], &w[i]); } solve(); } return 0; }