GYM - 101147 C.The Wall

题意：

　　长和宽分别为M+N/2，N的矩形中。有很多敌人的点。有两种方法消灭敌人。

　　1.N个桶，第i个桶可以消灭i-1<=x<i中的敌人。2.M个摆（半圆）每个摆可以消灭距离他前面不超过1以内的敌人。第i个摆的圆心在（N/2，i-1），半径都为N/2。

　　问消灭所有敌人消耗的最少设备是多少。

题解：

　　根据题意可以发现，每一个敌人都可以被桶消灭，但不一定被摆消灭。摆的盲区在第1个摆的内部和第M个摆两边的死角位置。

　　所以出现在盲区的点必须被桶消灭。即那些桶是必选的。

　　其余的点把消灭他的桶号和消灭他的摆号连边，跑一个最小顶点覆盖即可。

#include <bits/stdc++.h>

using namespace std;

int t;

int p;

double n, m;

int ans;

int vp[];

int vis[];

int match[];

struct ndoe {

    double x, y;

}w[];

double distance(double x1, double y1, double x2, double y2) {

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

vector<int> g[];

bool dfs(int u) {

    for(int i = ; i < g[u].size(); i++) {

        int v = g[u][i], w = match[v];

        if(vis[v]) continue;

        vis[v] = ;

        if(w< || dfs(w)) {

            match[v] = u;

            return true;

        }

    }

    return false;

}

int hungarian() {

    int res = ;

    memset(match, -, sizeof(match));

    for(int u = ; u < n; u++) {

        memset(vis, , sizeof(vis));

        if(dfs(u)) res++;

    }

    return res;

}

int main() {

    freopen("wall.in","r",stdin);

    scanf("%d", &t);

    while(t--) {

        ans = ;

        memset(vp, , sizeof(vp));

        scanf("%lf%lf%d", &n, &m, &p);

        for(int i = ; i < n+m; i++) g[i].clear();

        for(int i = ; i <= p; i++) scanf("%lf%lf", &w[i].x, &w[i].y);

        memset(vis, , sizeof(vis));

        for(int i = ; i <= p; i++) {

            if(distance(n/, , w[i].x, w[i].y)<=n/ || (w[i].y>m && distance(n/, m-, w[i].x, w[i].y)>1.0+n/)) {

                vp[i] = ;

                int v = (int)floor(w[i].x);

                if(vis[v]) continue;

                else {

                    vis[v] = ; ans++;

                }

            }

        }

        for(int i = ; i <= p; i++) {

            if(vp[i]) continue;

            int judge = (int)floor(w[i].x);

            if(vis[judge]) continue;

            int up = (int)floor(w[i].y);

            for(int v = up; v >= ; v--) {

                if(distance(n/, (double)v, w[i].x, w[i].y) > n/) {

                    int u = (int)floor(w[i].x);

                    g[u].push_back(v+n);

                    break;

                }

            }

        }

        ans += hungarian();

        printf("%d\n", ans);

    }

}

巴特西

GYM - 101147 C.The Wall

最新文章

热门文章