传送门[洛谷]

常见套路？

关键点连新建汇点 流量1 源点1 原图中的边 二分流量。

二分+判满流

做完了。

附代码。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define inf 20021225

#define ll long long

#define mxm 251000

#define mxn 510

using namespace std;

struct edge{int to,lt,f;}e[mxm];

int in[mxn],cnt,dep[mxn],s,t;queue<int> que;

void add(int x,int y,int f)

{

	e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;e[cnt].f=f;

	e[++cnt].to=x;e[cnt].lt=in[y];in[y]=cnt;e[cnt].f=0;

}

bool bfs()

{

	memset(dep,0,sizeof(dep));

	dep[s]=1;while(!que.empty())	que.pop();

	que.push(s);

	while(!que.empty())

	{

		int x=que.front();que.pop();

		for(int i=in[x];i;i=e[i].lt)

		{

			int y=e[i].to;if(dep[y]||!e[i].f)	continue;

			dep[y]=dep[x]+1;que.push(y);

			if(y==t)	return true;

		}

	}

	return false;

}

int dfs(int x,int flow)

{

	if(x==t||!flow)	return flow;

	int cur=flow;

	for(int i=in[x];i;i=e[i].lt)

	{

		int y=e[i].to;

		if(dep[y]==dep[x]+1&&e[i].f)

		{

			int tmp=dfs(y,min(e[i].f,cur));

			e[i].f-=tmp;e[i^1].f+=tmp;cur-=tmp;

			if(!cur)	return flow;

		}

	}

	dep[x]=-1;return flow-cur;

}

void init()

{

	cnt=1;

	memset(in,0,sizeof(in));

}

int dinic()

{

	int ans=0;

	while(bfs())	ans+=dfs(s,inf);

	//printf("%d\n",ans);

	return ans;

}

int u[mxm],v[mxm],h[mxn],n,m,k;

bool check(int mid)

{

	init();//printf("*%d ",mid);

	for(int i=1;i<=k;i++)	add(h[i],t,1);

	for(int i=1;i<=m;i++)	add(u[i],v[i],mid),add(v[i],u[i],mid);

	if(dinic()>=k)	return 1;

	return 0;

}

int main()

{

	int T,l,r,mid,ans;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&n,&m,&k);

		s=1;t=n+1;

		for(int i=1;i<=k;i++)	scanf("%d",&h[i]);

		for(int i=1;i<=m;i++)	scanf("%d%d",&u[i],&v[i]);

		l=1;ans=r=n;

		while(l<=r)

		{

			mid=l+r>>1;

			if(check(mid))	r=mid-1,ans=mid;

			else	l=mid+1;

		}

		printf("%d\n",ans);

	}

	return 0;

}