CF852D 【Exploration plan】
题目大意： 给定一个 v 个点 e 条边的带权无向图，在图上有 n 个人，第 i 个人位于点 xi，一个人通过一条边需要花费这条边的边权的时间。现在每个人可以自由地走。求最短多少时间后满足结束后有人的节点数 ≥ k
虽然我wa了几个点，但问题不大。
我们可以二分时间，然后建图跑网络流。
具体如下：
1.先floyd预处理一遍。
2.二分时间，对于每个有人的点，向时间内能到的点连边，流量为1
3.超级源点向有人的点连边流量为1，所有点向超级汇点连边，流量为1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1e9;
const int N=2e5+5;
struct node
{
int next,to,w;
}a[N];
int v,e,n,s,t,k;
int head[N],cnt,b[N],c[N],w[N],x[N],dis[666][666];
int cur[N],d[N];
queue <int> q;
void add(int x,int y,int dis)
{
a[++cnt].next=head[x];
a[cnt].to=y;
a[cnt].w=dis;
head[x]=cnt;
}
bool bfs(int s,int t)
{
memset(d,0x7f,sizeof(d));
while(!q.empty()) q.pop();
for(int i=s;i<=t;i++) cur[i]=head[i];
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=a[i].next)
{
int v=a[i].to;
if(d[v]>inf&&a[i].w)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
if(d[t]<inf) return true;
else return false;
}
int dfs(int now,int t,int limit)
{
if(!limit||now==t) return limit;
int flow=0,f;
for(int i=cur[now];i;i=a[i].next)
{
cur[now]=i;
int v=a[i].to;
if(d[v]==d[now]+1&&(f=dfs(v,t,min(limit,a[i].w))))
{
flow+=f;
limit-=f;
a[i].w-=f;
a[i^1].w+=f;
if(!limit) break;
}
}
return flow;
}
bool check(int mid)
{
//重新建图
cnt=1;
memset(head,0,sizeof(head));
memset(cur,0,sizeof(cur));
memset(d,0,sizeof(d));
//对于每个有人的点，向时间内能到的点连边，流量为1
for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
if(dis[x[i]][j]<=mid) add(x[i],j,1),add(j,x[i],0);
s=0,t=v+1;
for(int i=1;i<=n;i++)
add(0,x[i],1),add(x[i],0,0);//超级源点向有人的点连边流量为1
for(int i=1;i<=v;i++)
add(i,t,1),add(t,i,0);//所有点向超级汇点连边，流量为1
int ans=0;
while(bfs(s,t)) ans+=dfs(s,t,inf); //网络流
if(ans>=k) return 1;
else return 0;
}
int main()
{
scanf("%d%d%d%d",&v,&e,&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&x[i]);
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
dis[i][j]=1e9;
for(int i=1;i<=e;i++)
{
scanf("%d%d%d",&b[i],&c[i],&w[i]);
dis[b[i]][c[i]]=dis[c[i]][b[i]]=min(dis[b[i]][c[i]],w[i]);
}
//floyd预处理最短路径
for(int k=1;k<=v;k++)
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
//二分时间
int l=0,r=1000000;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}