二分答案，判断时间mid内能否解决问题
利用vector建边，不用管标号的冲突，在二分图中十分方便（一般网络流可能就没办法了）
时间复杂度：\(O(n^4*log(T))\) 实际更快 #include<bits/stdc++.h> using namespace std; #define go(i,a,b) for(int i=a;i<=b;++i) #define com(i,a,b) for(int i=a;i>=b;--i) #define mem(a,b) memset(a,b,sizeof(a)) const int inf=0x3f3f3f3f,N=60,M=2510; const double eps=1e-8; typedef long long ll; int n,m,v,match[M],tot; bool vis[M]; double t1,t2; vector<int>e[N]; struct node{ double x,y; }a[N],b[N]; struct new_node{ int id;double t; }c[M]; bool dfs(int u){ for(int i=0;i<e[u].size();++i){ int v=e[u][i]; if(vis[v]) continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u; return 1; } } return 0; } double dis(const node &x,const node &y){ return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)); } bool pd(double mid){ mem(match,0); go(i,1,m){ e[i].clear(); go(j,1,tot)//代表n*m颗导弹（不一定每个都发出，但最多这么多） if(c[j].t+dis(a[i],b[c[j].id])/v<=mid) e[i].push_back(j); } go(i,1,m){ mem(vis,0); if(!dfs(i)) return 0; } return 1; } signed main(){ //freopen("input.txt","r",stdin); scanf("%d%d%lf%lf%d",&n,&m,&t1,&t2,&v); tot=n*m; t1/=60; go(i,1,m) scanf("%lf%lf",&a[i].x,&a[i].y); go(i,1,n) scanf("%lf%lf",&b[i].x,&b[i].y); int k; go(i,1,m) go(j,1,n){ k=(i-1)*n+j; c[k].id=j; c[k].t=(i-1)*(t1+t2)+t1; } double l=t1,r=100000; while(r-l>eps){ double mid=(l+r)*0.5; if(pd(mid)) r=mid; else l=mid; } printf("%.6lf",r); return 0; }AcWing374 导弹防御塔
标签：
原文地址：https://www.cnblogs.com/White-star/p/11526325.html