Hlg 1481 二分图匹配+二分.cpp

题意：

一个船队 VS 一只章鱼

给出 n 个定点<章鱼头+章鱼手> 再给出 p 个可移动点<船长+船员>..

对于 n 个定点给出坐标 x y

对于 p 个可移动点给出坐标 x y 和速度 v

先输入 T 组样例..

对于定点 n 第一个给出章鱼头坐标接下来n-1行是每只章鱼手的坐标

对于移动点 p 第一个给出船长的信息接下来p-1行是每个船员的信息

思路：

二分图匹配..

所谓最快时间内让船长击打到章鱼头就是找出某个船员到章鱼手的最长时间

所以二分查找每个船员到对应章鱼手的花费时间..

如果以这个时间作为最长时间..那么就把比船员-章鱼手花费它时间少的连线..求最大匹配..匹配结果==章鱼手数的时候..

就继续二分..确保精确值..

答案就是这个时间+船长到章鱼头花费的时间..

Tips：

类型一定要明确好..已经不是第一次出现类型隐式转换导致数值改变的问题了.

这样的二分可以确定精确值..

二分的时候..什么时候左移..什么时候右移..

Code：

View Code

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <cmath>
  4 using namespace std;
  5 #define clr(x) memset(x, 0, sizeof(x))
  6 const int INF = 0x1f1f1f1f;
  7 
  8 struct Node
  9 {
 10     double x;
 11     double y;
 12     double v;
 13 }pir[110], ten[110], ca, he;
 14 
 15 struct Edge
 16 {
 17     int next;
 18     int to;
 19 }edge[1000000];
 20 int tot;
 21 int head[110];
 22 
 23 void add(int s, int u)
 24 {
 25     edge[tot].to = u;
 26     edge[tot].next = head[s];
 27     head[s] = tot++;
 28 }
 29 
 30 int link[110], vis[110];
 31 double v[110][110];
 32 int sum;
 33 int n, p;
 34 double l, r, mid;
 35 
 36 int dfs(int x)
 37 {
 38     for(int i = head[x]; i != 0; i = edge[i].next) {
 39         int y = edge[i].to;
 40         if(!vis[y]) {
 41             vis[y] = true;
 42             if(link[y] == 0 || dfs(link[y])) {
 43                 link[y] = x;
 44                 return true;
 45             }
 46         }
 47     }
 48     return false;
 49 }
 50 
 51 void solve()
 52 {
 53     clr(link);
 54     sum = 0;
 55     for(int i = 1; i <= n; ++i) {
 56         clr(vis);
 57         if(dfs(i))
 58             sum++;
 59     }
 60 }
 61 
 62 double dis(Node a, Node b)
 63 {
 64     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 65 }
 66 
 67 bool check(double t)
 68 {
 69     tot = 1;
 70     clr(head);
 71     for(int i = 1; i <= n; ++i)
 72         for(int j = 1; j <= p; ++j) {
 73             if(v[i][j] < t)// ?<=
 74                 add(i, j);
 75     }
 76     solve();
 77     if(sum == n)
 78         return true;
 79     else return false;
 80 }
 81 
 82 double solvee()
 83 {
 84     l = 0;
 85     while(l < r) {
 86         mid = (l+r)/2;
 87         if(check(mid)) r = mid-0.0000000001;
 88         else l = mid+0.0000000001;
 89     }
 90     return l;
 91 }
 92 
 93 int main()
 94 {
 95     int i, j, k;
 96     int T;
 97     //freopen("E:\\ACM\\Mess\\stdin-stdout\\in.txt", "r", stdin);
 98     scanf("%d", &T);
 99     while(T--)
100     {
101         clr(v);
102         r = 0;
103 
104         scanf("%d %d", &n, &p);
105         scanf("%lf %lf %lf", &ca.x, &ca.y, &ca.v);
106         for(i = 1; i <= p; ++i)
107             scanf("%lf %lf %lf", &pir[i].x, &pir[i].y, &pir[i].v);
108         scanf("%lf %lf", &he.x, &he.y);
109         for(i = 1; i <= n; ++i) {
110             scanf("%lf %lf", &ten[i].x, &ten[i].y);
111         }
112 
113         for(i = 1; i <= n; ++i)
114         for(j = 1; j <= p; ++j) {
115             v[i][j] = dis(pir[j], ten[i])/pir[j].v;
116             if(v[i][j] > r) r = v[i][j];
117         }
118         double ans = solvee()+dis(ca, he)/ca.v;
119         printf("%.9lf\n", ans);
120     }
121     return 0;
122 }