题意：给你N个的任务一定要在每天的[Li,Ri]时段完成，然后你只有K天的时间，每个任务有个val，然后求K天里能够获得的最大bonus。
思路：拿到手第一直觉是最小费用最大流，然后不会建图，就跑去想dp去了。好吧最小费用最大流的做法是这样的。首先题目给的是时间，所以变成整数的区间再离散化是一个标准姿势啦。然后对于相邻的时间点 1，2，3，4顺次建立这样的边 1->2->3->4...，边的容量为inf,费用为0.然后对于源点s，我们向时间点1连一条容量为k，费用为0的边，目的是限流。最后由最后一个时间点向汇点t连一条容量为inf,费用为0的边。然后对于每个事件，li,ri,vi,由时间点li->ri连容量为1费用为-vi的边。跑一遍最大流就可以了，最后的答案取个相反数（因为这里其实是最大费用最大流）。考虑一下正确性，首先一定是可以满流的，然后对于每条流出的流量，它只能往右走不能往左走，保证了区间不相交，所以最后跑出来的就是答案。
#pragma warning(disable:4996)#include#include #include #include #include #include #include #include #define ll long long#define maxn 10000#define maxe 30000#define inf 0x3f3f3f3fusing namespace std;struct Edge{ int u, v, nxt, cap, cost;}edge[maxe];int head[maxn];int n, m;int k;int siz;struct MinCostMaxFlow{ queue que; int add; // edges number int vn; // total vertex number int cost[maxn], in[maxn], pre[maxn]; bool vis[maxn]; void init(){ add = 0; vn = siz + 10; memset(head, -1, sizeof(head)); while (!que.empty()) que.pop(); } void insert(int u, int v, int w, int c){ edge[add].u = u; edge[add].v = v; edge[add].cap = w; edge[add].cost = c; edge[add].nxt = head[u]; head[u] = add++; edge[add].u = v; edge[add].v = u; edge[add].cap = 0; edge[add].cost = -c; edge[add].nxt = head[v]; head[v] = add++; } bool spfa(int s, int e){ memset(cost, 0x3f3f3f3f, sizeof(cost)); memset(in, 0, sizeof(in)); memset(vis, 0, sizeof(vis)); cost[s] = 0; pre[s] = -1; que.push(s); vis[s] = true; in[s]++; while (!que.empty()){ int u = que.front(); que.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = edge[i].nxt){ int v = edge[i].v; if (edge[i].cap > 0 && cost[v] > cost[u] + edge[i].cost){ cost[v] = cost[u] + edge[i].cost; pre[v] = i; if (!vis[v]){ que.push(v); vis[v] = true; in[v]++; if (in[v] > vn) return false; } } } } if (cost[e] < inf) return true; else return false; } int mincostmaxflow(int s, int e){ int mincost = 0, maxflow = 0; while (spfa(s, e)){ int flow = inf; for (int i = pre[e]; i != -1; i = pre[edge[i].u]){ flow = min(flow, edge[i].cap); } maxflow += flow; for (int i = pre[e]; i != -1; i = pre[edge[i].u]){ edge[i].cap -= flow; edge[i ^ 1].cap += flow; } mincost += cost[e] * flow; } return mincost; }}net;struct Seg{ int l, r; int val;}seg[maxn];int dis[maxn]; int top;int main(){ while (cin >> n >> k){ int hi, mi, si; top = 0; for (int i = 0; i < n; i++){ scanf("%d:%d:%d", &hi, &mi, &si); seg[i].l = hi * 60*60 + mi * 60 + si; dis[top++] = seg[i].l; scanf("%d:%d:%d", &hi, &mi, &si); seg[i].r = hi * 60*60 + mi * 60 + si; dis[top++] = seg[i].r; scanf("%d", &seg[i].val); } sort(dis, dis + top); siz = unique(dis, dis + top) - dis; for (int i = 0; i < n; i++){ seg[i].l = lower_bound(dis, dis + siz, seg[i].l) - dis + 1; seg[i].r = lower_bound(dis, dis + siz, seg[i].r) - dis + 1; } net.init(); int s = siz + 1, t = s + 1; for (int i = 1; i <= siz - 1; i++) net.insert(i, i + 1, inf, 0); net.insert(s, 1, k, 0); net.insert(siz, t, inf, 0); for (int i = 0; i < n; i++){ net.insert(seg[i].l, seg[i].r, 1, -seg[i].val); } cout << -net.mincostmaxflow(s, t) << endl; } return 0;}