ZOJ 3460 二分 + 二分匹配
题意：
n个炮塔 m个目标 炮弹装填时间t1 炮塔CD时间t2 炮弹速度
m个目标坐标
n个炮塔坐标
问最少需要多少时间打爆所有目标
思路：
二分查找需要的时间， 对于一个时间，二分匹配判断是否存在这样时间内的打击可以打爆所有炮塔
此时注意 炮塔可能打好几个目标，所以把炮塔拆成不同时间的炮塔
因为炮塔出导弹的时间是固定的，所以可以确定 tt [ i ] [ j ]表示 i 炮塔攻击 j 目标需要的时间
把 i 拆炮塔按时间拆成 i , i + m , i + 2*m , i + k*m ，表示i炮塔第k次攻击j目标
注意审题和拆点
#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#define N 55#define eps 1e-8using namespace std;struct node{double x,y;}a[N],b[N];double dis(node a,node b){return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));}int n,m;double t1,t2,v, timemax;double d[N][N], tt[N*N][N];int lef[N*N];bool T[N*N];vector<int>G[N];bool match(int x){for(int i = 0; i < G[x].size() ; i++){int v = G[x][i];if(T[v])continue;T[v] = true;if(lef[v] == -1 || match(lef[v])){lef[v] = x;return true;}}return false;}bool solve(){memset(lef, -1, sizeof(lef));for(int i = 0; i < m; i++){memset(T, 0, sizeof(T));if( !match(i) )return false;}return true;}double zouni(){int i, j;double l = 0, r = 100000000000, mid;while( l + eps < r ){mid = (l+r)/2;for(i = 0; i < m; i++)G[i].clear();for(i = 0; i < m; i++)for(j = 0; j < n*m; j++){if(tt[j][i] <= mid) G[i].push_back(j);}if(solve()) r = mid;elsel = mid;}return r;}int main(){int i, j, k;// n 为发射塔个数 m为目标while(~scanf("%d %d %lf %lf %lf",&n,&m,&t1,&t2,&v)){t1 /= 60; for(i = 0; i < m; i++)scanf("%lf %lf",&b[i].x,&b[i].y);for(i = 0; i < n; i++)scanf("%lf %lf",&a[i].x,&a[i].y);for(i = 0; i < n; i++)for(j = 0; j < m; j++)d[i][j] = dis(a[i],b[j])/v;for(i = 0; i < n; i++)for(j = 0; j < m; j++)for(k = 0; k < m; k++){tt[ i*m + k ][ j ] = (k+1)*t1 + k*t2 + d[i][j];}printf("%.6lf\n",zouni());}return 0;}/*3 3 30 20 10 00 5050 050 500 10001000 0*/