二分图

此题看书的时候觉得特别难，实际的代码却非常简单

现在分析是什么让代码如此简单的：

1. 首先预处理出第i个防御塔发射第j个导弹的时间（计算发射时间，不计冷却时间）

2. 二分答案，判断时间mid内能否解决问题

3. 利用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;}