首页 > ACM题库 > HDU-杭电 > HDU 4606-Occupy Cities-计算几何-[解题报告]HOJ
2015
09-17

HDU 4606-Occupy Cities-计算几何-[解题报告]HOJ

Occupy Cities

问题描述 :

The Star Wars is coming to an end as the Apple Planet is beaten by the Banana Planet. Captain Chen, the glorious leader of the Army of Banana Planet, has drawn up a plan to occupy all the cities on the Apple Planet. The Army of Banana Planet totally has P soldiers, and thus, Captain Chen can only conduct at most P soldiers to occupy the cities.
The cities on the planet can be regarded as points on a 2D plane. What’s more, there are some barriers on the planet, which can be seen as segments on the plane. When a soldier moves from city to city, he’s not allowed to cross or touch the barriers. However, the soldiers are smart enough to go along the shortest paths between cities.
But these soldiers are just soldiers, whereupon they also need food to replenish their energy. A soldier needs one unit of food to move one unit of distance forward. Fortunately, all the cities have sufficient food supplies. When a soldier steps in a city, he will fill up his food bag. Invaders as they are, the soldiers will burn up all the food after filling his bag. And thus, each city can supply only one soldier.
When a soldier steps in a city, this city is occupied by the Army of Banana Planet immediately. Soldiers can also just pass by a city but not step in. In this case, this city is not occupied yet, and the food in the city would not be burned.
Captain Chen has an occupying schedule for his soldiers. If city A is arranged before city B on the schedule, city A must be occupied before city B. All the soldiers will strictly follow this schedule. During the occupying process, soldiers can be air-dropped to any positions on the plane as needed. After a soldier lands on the ground, he can only move on foot, and replenish his energy by the food in his bag. Note that their bags are full of food initially, and all bags have the same volume for soldiers.
You, the logistics minister of the army, are required to help the Captain to cut down the cost and determine the minimal volume of all P soldiers’ food bags to finish occupying. All the requirements above should be fulfilled for sure.

输入:

The first line contains an integer T(T≤50), indictaing the number of test cases.
Each test case begins with three integers n(0<n≤100), m(0≤m≤100) and p(0<p≤100), which respectively denotes the number of cities, barriers and soldiers.
The following n lines describe the cities’ coordinates (x_i,y_i).
The next m lines, each with two pairs of integers (sxi,syi) and (exi,eyi), describe the two endpoints of each barrier.
The last line of each test case consists of n integers, describing the occupying schedule in order.
All the coordinates range from -10000 to 10000, and cities are labeled from 1 to n. You may assume that any two barriers will not have common points and cities will not be built on barriers.

输出:

The first line contains an integer T(T≤50), indictaing the number of test cases.
Each test case begins with three integers n(0<n≤100), m(0≤m≤100) and p(0<p≤100), which respectively denotes the number of cities, barriers and soldiers.
The following n lines describe the cities’ coordinates (x_i,y_i).
The next m lines, each with two pairs of integers (sxi,syi) and (exi,eyi), describe the two endpoints of each barrier.
The last line of each test case consists of n integers, describing the occupying schedule in order.
All the coordinates range from -10000 to 10000, and cities are labeled from 1 to n. You may assume that any two barriers will not have common points and cities will not be built on barriers.

样例输入:

2

2 1 1
0 0
2 0
1 1 1 -1
2 1

4 2 2
0 1
5 1
8 0
1 -1
0 0 2 0
6 0 6 3
1 2 3 4

样例输出:

2.83
3.41
Hint
For the second sample case, the best strategy is: step 1: air-drop soldier 1 to city 1, city 1 occupied; step 2: air-drop soldier 2 to city 2, city 2 occupied; step 3: soldier 2 moves from city 2 to city 3, city 3 occupied, and 3.41 units of food needed; step 4: soldier 1 moves from city 1 to city 4, city 4 occupied, and 2.41 units food needed. Therefore, the minimal volume of bags is 3.41.

题目大意如下

在一个二维坐标系中,有n个城市,坐标给出来了,然后有p个士兵要去占领这n个城市,但是路上有m个路障,都是线段,士兵不能越过路障前进。

每个士兵都有相同容量大小的一个干粮袋,每到一个城市他就能补充满自己的干粮袋。中途走路时走一个单位长度就消耗一个单位的干粮。

现在问的是这些个干粮袋最小的容量是多少,前提是保证p个士兵能占领完这n个城市,城市被占领顺序也是题目给好的,必须遵守

思路:P个士兵占领n个城市,可以看成p个士兵走出了p个路径,覆盖了所有的点。   但是题目没要求每个士兵都必须去占领。 也就是只要最小路径覆盖小于等于p个就代表所有的城市能被p个士兵去占领了。

最小路径覆盖的要求之一就是有向,无环,在题目中的体现就是城市被占领时必须有顺序。

这就符合一个拓扑序列了。所以就可以进行最小路径覆盖

然后整体的步骤就是,刚开始把各个点之间的距离先算出来,因为有障碍,所以必须把这些线段的两个端点都加入到点集中一块算,预处理两点距离时,就看两点之间有没有线段挡着,挡着就先按不可达算,注意处理线段交的时候端点相交不要管,因为还是可以过去。  没挡着就按照直线距离算。 然后floyd处理一下,任意两点之间的距离就算出来了

算出来后我们就要求干粮袋的容量了,一般的方法就是二分求可行性。 

对于二分的一个值,我们就建立一遍图,任意两点的距离不大于这个值才可以连边。

当然注意我们是按照题目中给的那个占领顺序,前边的可以向后边的连边,反之不能

然后求路径覆盖。判断是否可行

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define eps 1e-8
#define MAXN 333
#define INF 1111111111
using namespace std;
typedef double TYPE;
struct POINT
{
    TYPE x;
    TYPE y;
    POINT() : x(0), y(0) {};
    POINT(TYPE _x_, TYPE _y_) : x(_x_), y(_y_) {};
    bool operator == (const POINT &p)const
    {
        return (fabs(x - p.x) < eps && fabs(y - p.y) < eps);
    }
}p[MAXN];
TYPE Distance(const POINT & a, const POINT & b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
struct SEG
{
    POINT a; //起点
    POINT b; //终点
    SEG() {};
    SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) {};
    bool operator == (const SEG &p)const
    {
        return (p.a == a && p.b == b) || (p.b == a && p.a == b);
    }
}seg[MAXN];
TYPE Cross(const POINT & a, const POINT & b, const POINT & o)
{
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
bool IsIntersect(const SEG & u, const SEG & v)
{
    return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) > 0) &&
           (Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) > 0) &&
           (max(u.a.x, u.b.x) > min(v.a.x, v.b.x)) &&
           (max(v.a.x, v.b.x) > min(u.a.x, u.b.x)) &&
           (max(u.a.y, u.b.y) > min(v.a.y, v.b.y)) &&
           (max(v.a.y, v.b.y) > min(u.a.y, u.b.y));
}
int seq[MAXN];
struct node
{
    int v, next;
}edge[MAXN * MAXN];
int e, head[MAXN], mark[MAXN], cx[MAXN], cy[MAXN], n, m, so;
double dis[MAXN][MAXN];
void insert(int x, int y)
{
    edge[e].v = y;
    edge[e].next = head[x];
    head[x] = e++;
}
int path(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(!mark[v])
        {
            mark[v] = 1;
            if(cy[v] == -1 || path(cy[v]))
            {
                cx[u] = v;
                cy[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int gao()
{
    int ans = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for(int i = 1; i <= n; i++)
    {
        memset(mark, 0, sizeof(mark));
        ans += path(i);
    }
    return ans;
}
void floyd(int n)
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
}
bool ok(double mid)
{
    e = 0;
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            if(dis[seq[i]][seq[j]] <= mid)
                insert(seq[i], seq[j] + n);
    int x = gao();
    if(n - x <= so) return true;
    return false;
}
void slove()
{
    double l = 0, r = INF;
    double ans = -1;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        if(ok(mid)) {ans = mid; r = mid;}
        else l = mid;
    }
    printf("%.2f\n", ans);
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &so);
        for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
        for(int i = 1; i <= m; i++)
        {
            scanf("%lf%lf%lf%lf", &seg[i].a.x, &seg[i].a.y, &seg[i].b.x, &seg[i].b.y);
            p[n + i * 2 - 1] = seg[i].a;
            p[n + i * 2] = seg[i].b;
        }
        for(int i = 1; i <= n; i++) scanf("%d", &seq[i]);
        for(int i = 1; i <= n + m * 2; i++)
            for(int j = 1; j <= n + m * 2; j++)
            {
                if(i == j) {dis[i][j] = 0; continue;}
                int flag = false;
                for(int k = 1; k <= m; k++)
                {
                    if(seg[k] == SEG(p[i], p[j])) continue;
                    if(IsIntersect(seg[k], SEG(p[i], p[j])))
                    {
                        flag = true;
                        break;
                    }
                }
                if(flag) dis[i][j] = INF;
                else dis[i][j] = Distance(p[i], p[j]);
            }

        floyd(n + m * 2);
        slove();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/9977733