[二分+匈牙利]zoj 3460：Missile
大致题意：
? ? 用n个导弹发射塔攻击m个目标。每个发射架在某个时刻只能为一颗导弹服务，发射一颗导弹需要准备t1的时间，一颗导弹从发射到击中目标的时间与目标到发射架的距离有关。每颗导弹发射完成之后发射架需要t2的时间进入下个发射流程。现在问最少需要多少时间可以击毁所有m个目标。
?
大致思路：
? ? 二分枚举这个最大时间的最小值，每次按照这个枚举的时间构出二分图，求最大匹配来判定枚举值是否符合要求。
?
#include<iostream>#include<cstring>#include<cmath>#include<cstdio>using namespace std;const int inf=1<<30;const double eps=1e-8;int N,M;double tt1,tt2,v;int mis[100][2],tar[100][2];double dis[3000][60];double getdis(int a,int b){ double tmp=(mis[a][0]-tar[b][0])*(mis[a][0]-tar[b][0])+(mis[a][1]-tar[b][1])*(mis[a][1]-tar[b][1]); double res=sqrt(tmp); return res;}void getinit(){ int i,j,k; for(i=1;i<=N;i++) // 枚举第i个发射塔 { for(j=1;j<=M;j++) //第i个发射塔的第j次发射 { for(k=1;k<=M;k++) //第j次发射，攻击第k个目标 { dis[(i-1)*M+j][k]=(j-1)*tt2+getdis(i,k)/v+j*tt1; } } }}int map[3000][60];bool vis[3000];int linkk[3000];int dfs(int s){ for(int i=1;i<=M;i++){ if(!vis[i]&&map[s][i]){ vis[i]=1; if(linkk[i]==-1||dfs(linkk[i])){ linkk[i]=s; return 1; } } } return 0;}bool check(double mid){// cout<<"check"<<mid<<endl; int i,j,res=0; memset(map,0,sizeof(map)); for(i=1;i<=N*M;i++) { for(j=1;j<=M;j++) { if(dis[i][j]<=mid) { map[i][j]=1; } } } memset(linkk,-1,sizeof(linkk)); for(i=1;i<=N*M;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))res++; } if(res==M)return 1; return 0;}int main(){ int i; while(scanf("%d%d%lf%lf%lf",&N,&M,&tt1,&tt2,&v)!=EOF) { tt1/=60.0; for(i=1;i<=M;i++) { scanf("%d%d",&tar[i][0],&tar[i][1]); } for(i=1;i<=N;i++) { scanf("%d%d",&mis[i][0],&mis[i][1]); } getinit(); double left=0,right=200000000,mid; while(right-left>=eps) { mid=(left+right)/2.0; if(check(mid))right=mid; else left= mid; } printf("%.6f\n",left); } return 0;}?