题解【CF852D Exploration plan】

传送门。

$\texttt{Description}$

给你 $v$ 个点 $e$ 条边的带权无向图，$n$ 个人位于若干个点上且可以地走，最少多长时间至少有 $m$ 个点上至少有一个人。

$\texttt{Solution}$

瞄了一眼题解才知道可以二分做。

直接做是不好做的，但是观察可得答案具有单调性，于是可以二分答案。

考虑二分一个 $k$，表示每个人的行走时间都不大于 $k$。

这样我们可以通过这个 $k$ 来建图，对于每个人与能走到的点连一条边。

连出来的图就是一个二分图了，左边是人，右边是图上的点，需要求的就是二分图最大匹配，因为一个人只能走到一个点上。

这样我们建立源点 $s$ 和汇点 $t$，对于 $s$ 连向每一个人，容量为 $1$，每个点连 $t$，容量同样为 $1$，跑一遍 $\text{Dinic}$ 即可。

另外需要预处理一个 $\Theta(n^3)$ 的 $\text{Floyd}$，建图时需要判断两点的距离是否不大于 $k$。

贴一下代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9+10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x0?x:-x;}
const int MAXN(520000);
const int MAXM(610);
int V,M,N,m;
int a[MAXN];
int G[MAXM][MAXM];
inline void Floyd()
{
	for(register int k=1;k<=V;k++)
		for(register int i=1;i<=V;i++)
			for(register int j=1;j<=V;j++)
				G[i][j]=Min(G[i][j],G[i][k]+G[k][j]);
	return;
}
struct E{int to,nxt,flow;};
E edge[MAXN];
int head[MAXN],tot(1);
int s,t;
inline void add(int u,int v,int f)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	edge[tot].flow=f;
	return;
}
inline void add_edge(int u,int v,int f)
{
	add(u,v,f);
	add(v,u,0);
	return;
}
int dep[MAXN];
queueq;
inline bool bfs()
{
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=edge[i].nxt)
		{
			E e=edge[i];
			if(!dep[e.to]&&e.flow)
			{
				dep[e.to]=dep[u]+1;
				q.push(e.to);
			}
		}
	}
	return dep[t];
} 
inline int dfs(int u,int in)
{
	if(u==t) return in;
	int out(0);
	for(register int i=head[u];i&∈i=edge[i].nxt)
	{
		E e=edge[i];
		if(e.flow&&dep[e.to]==dep[u]+1)
		{
			int now=dfs(e.to,Min(e.flow,in));
			edge[i].flow-=now;
			edge[i^1].flow+=now;
			in-=now;
			out+=now;
		}
	}
	if(!out) dep[u]=0;
	return out;
}
inline void Clear()
{
	tot=1;
	memset(head,0,sizeof(head));
	memset(edge,0,sizeof(edge));
	return;
}
inline bool check(int lim)
{
	Clear();
	int ans(0);
	for(register int i=1;i<=N;i++)
		for(register int j=1;j<=V;j++)
			if(G[a[i]][j]<=lim) add_edge(i,j+N,1);
	for(register int i=1;i<=N;i++) add_edge(s,i,1);
	for(register int i=1;i<=V;i++) add_edge(i+N,t,1);
	while(bfs()) ans+=dfs(s,INF);
	return ans>=m;	
}
int main()
{
	V=read(),M=read(),N=read(),m=read();
	s=0,t=V+N+1;
	for(register int i=1;i<=N;i++) a[i]=read();
	for(register int i=1;i<=V;i++)
		for(register int j=1;j<=V;j++) if(i!=j)
			G[i][j]=INF;
	for(register int i=1;i<=M;i++)
	{
		int u=read(),v=read(),w=read();
		G[u][v]=G[v][u]=Min(G[u][v],w);
	}
	Floyd();
	int l=0,r=10000000,res(-1);
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1,res=mid;
		else l=mid+1;
	}
	printf("%d\n",res); 
	return 0;
}

$$\texttt{The End.by UF}$$