首页 > ACM题库 > HDU-杭电 > HDU 3126-Nova[解题报告]HOJ
2014
03-03

HDU 3126-Nova[解题报告]HOJ

Nova

问题描述 :

The Lich is a powerful hero that he can kill a wisp with his skill Frost Nova. The Burning Legion wants to conquer the forest so they sent some liches to kill all the wisps. A lich can kill a wisp once he could see the wisp and the wisp in his attack range. So the lich can attack a wisp when the distance between them is less than or equal to specific R and no trees are on the segment between the lich and wisp. Each lich has a cool down time that once he used Frost Nova he has to wait a few seconds for the next attack. Different liches may have different attack range and cool down time. The Lich King is the leader of the Burning Legion and he wants to arrange the attack order so the liches can wipe out all the wisps as soon as possible.

输入:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, M, K, indicating the number of lich, the number of wisps and the number of trees. The next N lines, each line consists of four integers x, y, r, t indicating the coordinate of that a lich, the radius of the attack range that lich’s Frost Nova can reach and the value of cool down time. The next M lines, each line consists of two integers x, y indicating the coordinate of each wisp. The last K lines, each line consists of three integers x, y, r, indicating the coordinate and radius of a tree. A lich cannot attack a wisp if the segment between them has a common point with the tree. The lich, wisp and trees will not overlap with each other.

输出:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, M, K, indicating the number of lich, the number of wisps and the number of trees. The next N lines, each line consists of four integers x, y, r, t indicating the coordinate of that a lich, the radius of the attack range that lich’s Frost Nova can reach and the value of cool down time. The next M lines, each line consists of two integers x, y indicating the coordinate of each wisp. The last K lines, each line consists of three integers x, y, r, indicating the coordinate and radius of a tree. A lich cannot attack a wisp if the segment between them has a common point with the tree. The lich, wisp and trees will not overlap with each other.

样例输入:

1
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

样例输出:

5

/*
 *  解法: 很明显是几何 + 最小费用最大流, 关键是如何建图.
 *        1. 设置一个源点和汇点.
 *        2. 每个lich和每个wisp分别用一个点来表示.
 *        3. 如果第i个lich能攻击到第j个wisp, 那么在图中从lich[i]到wisp[j]增加一条边, 容量为1, 费用为0.
 *        4. 每个wisp连一条边到汇点, 容量为1, 费用为0.
 *        5. 源点到每个lich连k条边, k为每个lich能攻击到的wisp数量, 每条边的容量为1, 第i条边的费用为i * t (i为0 - k-1, t为lich的cooldown时间)
 *        运行最小费用最大流, 答案就是从源点到lich满流的边, 且费用最大的那条边的费用值.
 */
#include <iostream>
#include <math.h>
using namespace std;
const int maxn = 205;
const double eps = 1e-8;
typedef int typef;
typedef int typec;
#define inff 0x0fffffff
#define infc 0x0fffffff
#define V    500
#define E    200000
struct network
{
    int nv, ne, pnt[E], nxt[E];
    int vis[V], que[V], head[V], pv[V], pe[V];
    typef flow, cap[E]; typec cost, dis[E], d[V];
    void addedge(int u, int v, typef c, typec w)
    {
        pnt[ne] = v; cap[ne] = c;
        dis[ne] = w; nxt[ne] = head[u]; head[u] = ne++;
        pnt[ne] = u; cap[ne] = 0;
        dis[ne] = -w; nxt[ne] = head[v]; head[v] = ne++;
    }
    int mincost(int src, int sink)
    {
        int i, k, f, r; typef mxf;
        for(flow = 0, cost = 0; ; )
        {
            memset(pv, -1, sizeof(pv));
            memset(vis, 0, sizeof(vis));
            for(i = 0; i < nv; ++i) d[i] = infc;
            d[src] = 0; pv[src] = src; vis[src] = 1;
            for(f = 0, r = 1, que[0] = src; r != f; )
            {
                i = que[f++]; vis[i] = 0;
                if(V == f) f = 0;
                for(k = head[i]; k != -1; k = nxt[k])
                    if(cap[k] && dis[k]+d[i] < d[pnt[k]])
                    {
                        d[pnt[k]] = dis[k] + d[i];
                        if(0 == vis[pnt[k]])
                        {
                            vis[pnt[k]] = 1;
                            que[r++] = pnt[k];
                            if(V == r) r = 0;
                        }
                        pv[pnt[k]] = i; pe[pnt[k]] = k;
                    }
            }
            if(-1 == pv[sink]) break;
            for(k = sink, mxf = inff; k != src; k = pv[k])
                if(cap[pe[k]] < mxf) mxf = cap[pe[k]];
            flow += mxf; cost += d[sink] * mxf;
            for(k = sink; k != src; k = pv[k])
            {
                cap[pe[k]] -= mxf; cap[pe[k]^1] += mxf;
            }
        }
        return cost;
    }
    void init(int v)
    {
        nv = v; ne = 0;
        memset(head, -1, 4 * v);
    }
} nw;
struct Lich
{
    double x, y, r;
    int t;
    void input()
    {
        scanf("%lf %lf %lf %d", &x, &y, &r, &t);
    }
} lich[maxn];
struct Wisp
{
    double x, y;
    void input()
    {
        scanf("%lf %lf", &x, &y);
    }
} wisp[maxn];
struct Tree
{
    double x, y, r;
    void input()
    {
        scanf("%lf %lf %lf", &x, &y, &r);
    }
} tree[maxn];
int T, N, M, K;
int ecnt[maxn];
double Dot(double dx1, double dy1, double dx2, double dy2)
{
    return dx1 * dx2 + dy1 * dy2;
}
double Dis(double x0, double y0, double x1, double y1, double x2, double y2)
{
    double a, b, c;
    if (fabs(x1 - x2) > fabs(y1 - y2))
    {
        b = 1.0;
        a = b * (y2 - y1) / (x1 - x2);
        c = -(a * x1 + b * y1);
    }
    else
    {
        a = 1.0;
        b = a * (x2 - x1) / (y1 - y2);
        c = -(a * x1 + b * y1);
    }
    return fabs(a * x0 + b * y0 + c) / sqrt(a * a + b * b);
}
bool NoCross(int a, int b)
{
    int i;
    for (i = 0; i < K; i++)
    {
        if (Dot(tree[i].x - lich[a].x, tree[i].y - lich[a].y, wisp[b].x - lich[a].x, wisp[b].y - lich[a].y) > 0.0 &&
            Dot(tree[i].x - wisp[b].x, tree[i].y - wisp[b].y, lich[a].x - wisp[b].x, lich[a].y - wisp[b].y) > 0.0 &&
            Dis(tree[i].x, tree[i].y, lich[a].x, lich[a].y, wisp[b].x, wisp[b].y) < tree[i].r + eps)
            return false;
    }
    return true;
}
bool InRound(int i, int j)
{
    double dx = lich[i].x - wisp[j].x;
    double dy = lich[i].y - wisp[j].y;
    return sqrt(dx * dx + dy * dy) < lich[i].r + eps;
}
void BuildGraph()
{
    int i, j;
    for (i = 0; i < N; i++)
    {
        ecnt[i] = 0;
        for (j = 0; j < M; j++)
        {
            if (InRound(i, j) && NoCross(i, j))
            {
                ecnt[i]++;
                nw.addedge(i, N + j, 1, 0);
            }
        }
    }
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < ecnt[i]; j++)
            nw.addedge(N + M, i, 1, lich[i].t * j);
    }
    for (i = 0; i < M; i++)
        nw.addedge(N + i, N + M + 1, 1, 0);
}
void Solve()
{
    nw.mincost(N + M, N + M + 1);
    if (nw.flow != M)
    {
        printf("-1/n");
        return;
    }
    int ans = 0;
    for (int p = nw.head[N+M]; p != -1; p = nw.nxt[p])
    {
        if (nw.cap[p] == 0 && nw.dis[p] > ans)
            ans = nw.dis[p];
    }
    printf("%d/n", ans);
}
int main()
{
    int i;
    for (scanf("%d", &T); T; T--)
    {
        scanf("%d %d %d", &N, &M, &K);
        for (i = 0; i < N; i++)
            lich[i].input();
        for (i = 0; i < M; i++)
            wisp[i].input();
        for (i = 0; i < K; i++)
            tree[i].input();
        nw.init(N + M + 2);
        BuildGraph();
        Solve();
    }
    return 0;
}

参考:http://blog.csdn.net/RaceBug2010/article/details/6092516


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。