Description

有一棵树，树上有些特殊点，每个不是特殊点的点有一个人，每个人走过一条边的时间为1。现在所有的人要走到特殊点上，每个点可以有多个人，但每条边每1时间只能走一个人。求所有人到达特殊点的最小时间。

Solution

考虑每个人应该走向哪个洞穴。假如一个人要到一个洞穴\(a_i\)，到达距离为\(d\)，把每个洞穴拆成\(n\)个点，如果还没有人要走到这个洞穴的第\(d\)号点，那么这个人可以走到这个点，如果已经被另一个人所走到，则可以匹配该洞穴的下一个点或下一个洞穴。要使所有洞穴被走到编号的最大值最小。

于是可以二分答案，于是转换成判定性问题，网络流或者匈牙利判一下有没有匹配即可。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define fo(i,j,k) for(int i=j;i<=k;++i)#define fd(i,j,k) for(int i=j;i>=k;--i)#define rep(i,x) for(int i=ls[x];i;i=nx[i])using namespace std;const int N=2010,maxn=1e5+10,M=4e5+10,inf=1e9;int to[M],nx[M],ls[maxn],vl[M],num=1;int S,T;int a[N];int n,m;bool bz[N];void link(int u,int v,int w){    to[++num]=v,nx[num]=ls[u],ls[u]=num;    vl[num]=w;    to[++num]=u,nx[num]=ls[v],ls[v]=num;    vl[num]=0;}vector
         
           e[N];int d[N][N],now;void dfs(int x,int fr,int t){ d[now][x]=t; int o=e[x].size(); fo(i,0,o-1) if(e[x][i]!=fr) dfs(e[x][i],x,t+1);}int h[maxn],q[maxn];bool bfs(){ int l=0,r=1; memset(h,0,sizeof(h)); h[q[1]=S]=1; while(l
          
           0;}int flow(int x,int t){ if(x==T) return t; int fl=t; rep(i,x){ int v=to[i]; if(!vl[i] || h[v]!=h[x]+1) continue; int tmp=flow(v,min(t,vl[i])); t-=tmp,vl[i]-=tmp,vl[i^1]+=tmp; if(!t) break; } if(fl==t) h[x]=-1; return fl-t;}bool check(int x){ memset(ls,0,sizeof(ls)); S=n+x*m+1,T=S+1; num=1; fo(i,1,m) fo(j,1,x){ link(i+n+(j-1)*m,T,1); if(j
           
            >1; check(mid)?r=mid:l=mid; } if(check(l)) r=l; printf("%d\n",r);}