记录编号	209974	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-11-24 19:27:04	内存使用	0.55 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	int ans = 0;
	while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
	return ans;
}
const int N = 1010, ml = 1000000000;
struct point {
	int x, y, z;
} a[N];
int q[N*10], d[N];
int find(int x, int n) {
	int l = 1, r = n;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (x == d[mid]) return mid;
		if (x > d[mid]) l = mid+1; else r = mid;
	}
	if (x == d[l]) return l; else return r;
}

struct edge {
	int x, y, z, w, next;
	edge(int x = 0, int y = 0, int z = 0, int w = 0, int next = -1): x(x), y(y), z(z), w(w), next(next) {}
} e[N*10];
int h[N], tot = 0;
void match(int x, int y, int z, int w) {
	e[tot] = edge(x, y, z, w, h[x]); h[x] = tot++;
	e[tot] = edge(y, x, 0, -w, h[y]); h[y] = tot++;
} 

int dist[N], ff[N], f[N];
int s, t;
bool spfa() {
	for (int i = 1; i <= t; i++) dist[i] = -ml; dist[s] = 0;
	int l = 1, r = 1; q[1] = s;
	memset(f, 0, sizeof(f)); f[s] = 1;
	while (l <= r) {
		int x = q[l], p = h[x];
		while (p != -1) {
			if (e[p].z && dist[x] + e[p].w > dist[e[p].y]) {
				dist[e[p].y] = dist[x] + e[p].w;
				ff[e[p].y] = p;
				if (!f[e[p].y]) {
					f[e[p].y] = 1;
					q[++r] = e[p].y;
				}
			}
			p = e[p].next;
		}
		f[q[l++]] = 0;
	}
	return (dist[t] > -ml);
}
int main() {
	freopen("interv.in", "r", stdin);
	freopen("interv.out", "w", stdout);
	int n = read(), k = read();
	int r = 0;
	for (int i = 1; i <= n; i++) {
		a[i].x = read(), a[i].y = read();
//		if (a[i].x > a[i].y) swap(a[i].x, a[i].y);
		a[i].z = a[i].y-a[i].x;
		q[++r] = a[i].x; q[++r] = a[i].y;
	}
	sort(q+1, q+r+1);
	int diff = 1; d[1] = q[1];
	for (int i = 2; i <= r; i++) if (q[i] != q[i-1]) d[++diff] = q[i];
	s = diff+1, t = s + 1;
	memset(h, -1, sizeof(h));
	
	match(s, 1, k, 0); match(diff, t, k, 0);
	for (int i = 1; i <= n; i++) a[i].x = find(a[i].x, diff), a[i].y = find(a[i].y, diff);
	for (int i = 1; i < diff; i++) match(i, i+1, ml, 0);
	for (int i = 1; i <= n; i++) match(a[i].x, a[i].y, 1, a[i].z);
	int ans = 0;
	while (spfa()) {
		int p = t, w = ml;
		while (p != s) {
			w = min(w, e[ff[p]].z);
			p = e[ff[p]].x;
		}
		ans += dist[t] * w;
		p = t;
		while (p != s) {
			e[ff[p]].z -= w;
			e[ff[p]^1].z += w;
			p = e[ff[p]].x;
		}
	}
	
	printf("%d\n", ans);
	return 0;
}