前言

本题解是这篇题解做法的优化（写法更简单）。基本思路与之相同，所不同的是可以不用每次重新创建一次图。

还有有一道题做法与之类似的题P4251。

题目描述

给定一个 $m$ 个点的无向图，每个点有点权，求是否可以用 $n+1$ 条边完全覆盖。如果不能，求出不能覆盖的点权的最大值最小是多少。

题解

别的题解已经写得很清楚了，这里就重复一遍。

对于能的情况就是先用 Floyd 跑出传递背包（就是能到达的点），然后对这两个点连边，问题就是对这个图求最小不相交路径覆盖问题。可以使用匈牙利算法。

对于不能的情况，很容易想到二分。

但是数据 $v \leq 10^9$ ，不能直接二分，先进行离散化。

然后根据上边的情况容易想到先前题解中的做法，即：把值比 $mid$ 大的点忽略掉，然后再建一个图和之前一样用二分图匹配。

一些改进

可以发现并不用每次重新建一次图，只需要每次判断每次待匹配的点的权值是否大于 $mid$ 即可，如果大于可能是不能到达，则跳过即可。这样子只需要定义一个全局变量 $mid$ ，然后每次找增广路的是否判断一下就行了。

代码实现

一个常见的技巧

每次匹配下一个点时候 $vis$ 数组不用清空，只需要记录一个时间戳 $tim$ ,每次判断 $vis_i=tim$ 就行了。如果相等就说明已经到达过了。

一些变动

因为题目给出的 $n,m$ 不太符合常规思维，所以在代码中用 $n$ 来表示题目数量。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1002;
int m,n,val[N],mat[N],vis[N],tim,mps[N][N],lis[N],cntv,lim;
void floyd(){//求传递背包
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				mps[i][j]|=(mps[i][k]&mps[k][j]);
}
bool findadp(int u){//常规二分图匹配匈牙利算法
	if(val[u]>=lim)return 0;
	for(int i=1;i<=n;++i){
		if(vis[i]==tim||!mps[u][i]||val[i]>=lim)continue;
		vis[i]=tim;
		if(!mat[i]||findadp(mat[i]))
			{mat[i]=u;return 1;}
	}return 0;
}
bool check(){
	int sum=0;tim=0;
	for(int i=1;i<=n;++i)if(val[i]<lim)++sum;//最多能获得的点
	memset(mat,0,sizeof(mat));
	memset(vis,-1,sizeof(vis));
	for(int i=1;i<=n;++i,++tim)
		sum-=findadp(i);
	return sum<=m+1;
}
int main(){
	scanf("%d%d",&m,&n);//注意这里和题目的m,n相反
	for(int i=1,t,v;i<=n;++i){
		scanf("%d%d",&val[i],&t);lis[i]=val[i];
		while(t--){scanf("%d",&v);mps[i][v]=1;}
	}
	floyd();//联通到达
	sort(lis+1,lis+1+n);//离散化
	cntv=unique(lis+1,lis+1+n)-lis-1;
	for(int i=1;i<=n;++i)val[i]=lower_bound(lis+1,lis+1+cntv,val[i])-lis;
	lim=cntv+1;//[1,lim) 左闭右开
	if(check()){puts("AK");return 0;}
	int l=1,r=cntv;
	while(l<r){//二分答案
		lim=(l+r+1)>>1;
		if(check())l=lim;
		else r=lim-1;
	}
	printf("%d\n",lis[l]);
	return 0;
}

题意

给出一个带权有向图，选出 $n+1$ 条链，问能否全部点覆盖，如果不能，问不能覆盖的点权最小值最大是多少。

分析

显然是在求 DAG 最少链覆盖。（不会的可以看我的博客）由于判定十分简单，考虑二分。

这里点出我自己思考时的一个小误区：二分即意味着要删掉所有权值较大的点，这会不会使得判定的结果不存在单调性？（因为不能经过那些点了）事实上，由于我们已经跑了一边传递闭包，上面的担忧是完全多余的。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 510, M = N * N;
int n, m, w[N], d[N][N];
int link[N];
bool vis[N];

int h[N], ne[M], e[M], idx;
void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void floyd()
{
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				d[i][j] |= d[i][k] & d[k][j];
}

bool dfs(int x, int s)
{
	for(int i = h[x]; i; i = ne[i])
		if(d[x][e[i]] && !vis[e[i]] && w[e[i]] <= s)
		{
			int j = e[i];
			vis[j] = 1;
			if(!link[j] || dfs(link[j], s))
			{
				link[j] = x;
				return 1;
			}
		}
	return 0;
}

bool check(int x)
{
	int ans = 0, sum = 0;
	memset(link, 0, sizeof(link));
	for(int i = 1; i <= n; i++)
		if(w[i] <= x)
		{
			sum++;
			memset(vis, 0, sizeof(vis));
			ans += dfs(i, x);
		}
	return sum - ans <= m;
}

int main()
{
	cin >> m >> n;
	m++;
	
	for(int i = 1; i <= n; i++) d[i][i] = 1;
	for(int i = 1, m, x; i <= n; i++)
	{
		scanf("%d%d", &w[i], &m);
		while(m--) scanf("%d", &x), d[i][x] = 1;
	}
	floyd();
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(i != j && d[i][j]) add(i, j);
		
	if(check(1e9))
	{
		puts("AK");
		return 0;
	}
	int l = 0, r = 1e9;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(check(mid)) l = mid + 1;
		else r = mid;
	}
	cout << l << endl;
	return 0;
}