「TJOI2018」智力竞赛（二分+DAG最小可相交路径覆盖）

https://loj.ac/problem/2574

这个题目描述扎心了。

简要题意：
用n+1条可以相交的路径去覆盖DAG，使得没被覆盖的点的权值的最小值最大。

首先二分答案，问题转换为有一些点一定要被覆盖，问n+1条路径内有没有解。

这个可以暴力费用流，每个点拆成两个点，\(i->i',r=1\)，如果这个点必选，则费用为inf，否则为0。
由于每个点还可以被额外经过无限次，所以再连\(i->i',r=inf,w=0\)。
若有边\((i,j)\)，则\(i'->j\)连边，每个点都可以作为终点或者起点，所以\(S->i,i'->T\)连边。
求总流量不超过n+1时的最大费用，看能不能把inf都选上。

事实上这是个经典问题：DAG路径覆盖问题

先Floyd传递闭包，只保留要被覆盖的点，跑dinic即可。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int inf = 1e9;

const int N = 505;

int n, m;
int v[N];

int f[N][N];

const int M = N * N * 3;

int fi[M], nt[M], to[M], r[M], tot = 1;
int S, T;

void link(int x, int y, int z) {
//	pp("%d %d %d\n", x, y, z);
	nt[++ tot] = fi[x], to[tot] = y, r[tot] = z, fi[x] = tot;
	nt[++ tot] = fi[y], to[tot] = x, r[tot] = 0, fi[y] = tot;
}

void cl() {
	fo(i, 1, T) fi[i] = 0;
	tot = 1;
}

int p[N], p0;

int d[M], d0, dis[M], cur[M];

int bfs() {
	fo(i, 1, T) dis[i] = inf;
	d[d0 = 1] = S; dis[S] = 0;
	for(int i = 1; i <= d0; i ++) {
		int x = d[i];
		cur[x] = fi[x];
		for(int j = fi[x]; j; j = nt[j]) if(r[j] && dis[to[j]] == inf) {
			dis[to[j]] = dis[x] + 1;
			d[++ d0] = to[j];
		}
	}
	return dis[T] < inf;
}

int dfs(int x, int flow) {
	if(x == T) return flow;
	int use = 0;
	for(int i = cur[x]; i; cur[x] = i = nt[i]) if(r[i] && dis[x] + 1 == dis[to[i]]) {
		int t = dfs(to[i], min(flow - use, r[i]));
		use += t, r[i] -= t, r[i ^ 1] += t;
		if(flow == use) return use;
	}
	return use;
}

int pd(int mi) {
	S = 2 * m + 1, T = S + 1;
	cl();
	p0 = 0;
	fo(i, 1, m) if(v[i] < mi) {
		p[++ p0] = i;
		link(S, i, 1);
		link(i + m, T, 1);
	}
	fo(i, 1, p0) fo(j, 1, p0) if(i != j && f[p[i]][p[j]] < inf) {
		link(p[i], p[j] + m, 1);
	}
	int sum = 0;
	while(bfs()) sum += dfs(S, 1 << 30);
	sum = p0 - sum;
	return sum <= n;
}

int main() {
	scanf("%d %d", &n, &m);
	n ++;
	fo(i, 1, m) fo(j, 1, m) if(i != j) f[i][j] = 1e9;
	fo(i, 1, m) {
		int k, j;
		scanf("%d %d", &v[i], &k);
		fo(u, 1, k) {
			scanf("%d", &j);
			f[i][j] = 1;
		}
	}
	fo(k, 1, m) fo(i, 1, m) fo(j, 1, m)
		f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	int as = 0;
	for(int l = 0, r = 1e9 + 1; l <= r; ) {
		int m = l + r >> 1;
		if(pd(m)) as = m, l = m + 1; else r = m - 1;
	}
	if(as > 1e9) pp("AK\n"); else {
		pp("%d\n", as);
	}
}