https://www.acwing.com/problem/content/376/

Dinic求二分图匹配

代码多点，但效率不低

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

const int N=55, M=N*N*N*2;
int ver[M],nxt[M],f[M],head[N*N],tot=1;
int n,m,S,T;
double T1,T2,V,dist[N][N],eps=1e-10;
int d[N*N], cur[N*N];
struct Node{int x,y;} a[N],b[N];

void add(int x,int y,int c){
    ver[++tot]=y, f[tot]=c, nxt[tot]=head[x],head[x]=tot;
    ver[++tot]=x, f[tot]=0, nxt[tot]=head[y],head[y]=tot;
}

bool bfs(){
    queue<int> q;
    q.push(S);
    memset(d,0,sizeof d);
    d[S]=1, cur[S]=head[S];
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=cur[x];i;i=nxt[i]){
            int y=ver[i];
            if(d[y] || !f[i])continue;
            d[y]=d[x]+1;
            cur[y]=head[y];
            if(y==T) return true;
            q.push(y);
        }
    }
    return false;
}

int find(int x,int limit){
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];i && flow<limit;i=nxt[i]){
        int y=ver[i];
        cur[x]=i;
        if(d[y]!=d[x]+1 || !f[i])continue;
        int k=find(y,min(f[i],limit-flow));
        if(!k)d[y]=0; //废掉y
        f[i]-=k, f[i^1]+=k, flow+=k;
    }
    return flow;
}

int dinic(){
    int flow,res=0;
    for(;bfs();)
        while(flow=find(S,1e9))res+=flow;
    return res;
}

bool check(double mid){
    int cnt=(mid+T2)/(T1+T2)+eps;
    cnt=min(cnt,m);
    memset(head,0,sizeof head);
    tot=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<cnt;k++)
                if((k+1)*T1+k*T2+dist[i][j]<mid-eps)
                    add(i,m+k*n+j,1);
    S=0, T=m+n*cnt+1;
    for(int i=1;i<=m;i++)
        add(S,i,1);
    for(int j=1;j<=n;j++)
        for(int k=0;k<cnt;k++)
            add(m+k*n+j,T,1); 
    int res=dinic();
    return res==m;
}

int main(){
    cin>>n>>m>>T1>>T2>>V;
    T1/=60;
    for(int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++) scanf("%d%d",&b[i].x,&b[i].y);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            dist[i][j]=hypot(a[i].x-b[j].x, a[i].y-b[j].y)/V; //dist: use time

    double l=0, r=1e9;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.6f\n",r);
}