Intervals poj3680 费用流

Description

---

在数轴上给一些线段l,r和线段的价值w，求任意一点不被覆盖超过k次的最大获利

Solution

---

好劲啊

一开始想的是每个点要连起来，然后一段线段拆开，结果打着打着自己都找出了反例 看了一波题解

首先覆盖一段是等同于覆盖左右两边，那么还是用容量为k费用为0的边连起所有点，然后线段的l和r连边容量为1费用为w

把问题转换以后就容易解决了，有些等价的变化还是很巧妙的，我果然还是太弱了

Code

---

#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <queue> #define rep(i, st, ed) for (int i = st; i <= ed; i += 1) #define erg(i, st) for (int i = ls[st]; i; i = e[i].next) #define fill(x, t) memset(x, t, sizeof(x)) #define pb push_back #define INF 0x3f3f3f3f #define N 501 #define E N * N + 1 struct seg{int l, r, w;}; struct data{int x, index;}; struct edge{int x, y, w, c, next;}; inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v; } edge e[E]; int ls[N]; inline void addEdge(int &cnt, int x, int y, int w, int c){ cnt += 1; e[cnt] = (edge){x, y, w, c, ls[x]}; ls[x] = cnt; cnt += 1; e[cnt] = (edge){y, x, 0, -c, ls[y]}; ls[y] = cnt; } using std:: queue; int inQueue[N], dis[N], pre[N]; inline int spfa(int st, int ed){ queue<int> que; que.push(st); fill(dis, -31); dis[st] = 0; fill(inQueue, 0); inQueue[st] = 1; int inf = dis[0]; while (!que.empty()){ int now = que.front(); que.pop(); erg(i, now){ if (e[i].w > 0 && dis[now] + e[i].c > dis[e[i].y]){ dis[e[i].y] = dis[now] + e[i].c; pre[e[i].y] = i; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; que.push(e[i].y); } } } inQueue[now] = 0; } return dis[ed] != inf; } inline int min(int x, int y){ return x<y?x:y; } inline int find(int ed){ int mn = INF, ret = 0; for (int i = ed; pre[i]; i = e[pre[i]].x){ mn = min(mn, e[pre[i]].w); ret += e[pre[i]].c; // printf("%d\n", e[pre[i]].c); } for (int i = ed; i; i = e[pre[i]].x){ e[pre[i]].w -= mn; e[pre[i] ^ 1].w += mn; } return ret * mn; } inline int mcf(int st, int ed){ int tot = 0; while (spfa(st, ed)){ tot += find(ed); } return tot; } inline int cmp(data a, data b){ return a.x < b.x; } using std:: vector; int hy[N], lx[N]; int main(void){ int T = read(); while (T --){ vector<data> v; vector<seg> s; int n = read(), k = read(); rep(i, 1, n){ int l = read(), r = read(), w = read(); v.pb((data){l, i * 2 - 1}); v.pb((data){r, i * 2}); s.pb((seg){i * 2 - 1, i * 2, w}); } sort(v.begin(), v.end(), cmp); fill(hy, 0); int cnt = 2; hy[v[0].index] = 1; rep(i, 1, v.size() - 1){ if (v[i].x != v[i - 1].x){ cnt += 1; } hy[v[i].index] = cnt; } cnt += 1; int edgeCnt = 1; fill(ls, 0); rep(i, 2, cnt){ addEdge(edgeCnt, i - 1, i, k, 0); } rep(i, 0, s.size() - 1){ addEdge(edgeCnt, hy[s[i].l], hy[s[i].r], 1, s[i].w); } int ans = mcf(1, cnt); printf("%d\n", ans); } return 0; }