BZOJ2965 保护古迹

2015.01.28 07:42 Wed| 6 visits oi_2015| 2015_刷题日常| Text

Solution

显然,注意到这道题的点数很少,如果将原图转化为对偶图,可以枚举被保护的古迹,之后分别暴力重新建图跑最小割出解。于是问题在于如何转化为对偶图以及找出题目中给出的古迹所在的位置。

对于每一个端点,按照极角将它的出边排序,之后枚举每一条边,如果它没被访问过,那么从这条边开始逆(顺)时针找到一个环,被这个环所包围的就是一个区域。由于这道题古迹数较少($\le 10$),只需要最暴力的暴力就可以得到每一个古迹所在区域。另外需要顺便用叉积判断当前搜到的区域是否是外界区域,就可以得到汇点的标号。经验证,此题不需要考虑凹多边形或回形区域的影响。

按照这一建图方法,样例如图所示。

Code

#include <bits/stdc++.h>
using namespace std;

#define P 11
#define N 805
#define M 1005
#define inf 0x3f3f3f3f

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int c, n, m, tot, belong[P], pre[N], vis[N], ans[N];

struct point { int x, y; } q[P], p[N];

inline long long cross(const point &a, const point &b, const point &c)
{
    return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (b.y - a.y) * (c.x - a.x);
}

struct line
{
    int x, y, z; double ang;
    line() {}
    line(int _x, int _y, int _z) : x(_x), y(_y), z(_z)
    { ang = atan2( p[_y].y - p[_x].y, p[_y].x - p[_x].x); }
    inline bool left(const point &t) const
    {
        return cross(p[x], p[y], t) >= 0;
    }
} l[N];

inline bool cmp(int x, int y)
{
    return l[x].ang < l[y].ang;
}

vector<int> v[N];

int head[N], cnt;

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

bool flag[P];
inline void check(int x)
{
    for (int i = 1; i <= c; ++i)
        if (!belong[i] && !l[x].left(q[i])) flag[i] = false;
}

int s, t, d[N];
bool bfs()
{
    memset(d, 0, sizeof d);
    queue<int> q;
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop();
        for (int i = head[x]; i; i = edge[i].next)
        {
            if (!edge[i].val || d[y = edge[i].to]) continue;
            d[y] = d[x] + 1;
            if (y == t) return true;
            q.push(y);
        }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f, y;
    for (int i = head[x]; i; i = edge[i].next)
    {
        if (!edge[i].val || d[y = edge[i].to] != d[x] + 1) continue;
        int k = dfs(y, min(edge[i].val, temp));
        if (!k) d[y] = 0;
        edge[i].val -= k, edge[i ^ 1].val += k;
        if (!(temp -= k)) break;
    }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

int main()
{
    cin >> c >> n >> m;
    for (int i = 1; i <= c; ++i) q[i].x = read(), q[i].y = read();
    for (int i = 1; i <= n; ++i) p[i].x = read(), p[i].y = read();
    for (int x, y, z, i = 0; i < m << 1; i += 2)
    {
        x = read(), y = read(), z = read();
        l[i] = line(x, y, z);
        v[x].push_back(i);
        l[i ^ 1] = line(y, x, z);
        v[y].push_back(i ^ 1);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!v[i].size()) continue;
        sort(v[i].begin(), v[i].end(), cmp);
        pre[v[i][0]] = v[i][v[i].size()-1];
        for (int j = 1; j < int(v[i].size()); ++j)
            pre[v[i][j]] = v[i][j-1];
    }
    for (int i = 0; i < m << 1; ++i)
    {
        if (vis[i]) continue;
        memset(flag, true, sizeof flag);
        vis[i] = ++tot, check(i);
        long long area = 0;
        for (int j = pre[i ^ 1]; j != i; j = pre[j ^ 1])
        {
            if (pre[j ^ 1] != i) area += cross(p[l[i].x], p[l[j].x], p[l[j].y]);
            vis[j] = tot, check(j);
        }
        if (area < 0) t = tot;
        for (int j = 1; j <= c; ++j)
            if (!belong[j] && flag[j]) belong[j] = tot;
    }
    s = tot + 1;
    memset(ans, 0x3f, sizeof ans);
    for (int i = 1; i < (1 << c); ++i)
    {
        int now = 0;
        memset(head, 0, sizeof head); cnt = 1;
        for (int j = 0; j < m << 1; ++j)
            add(vis[j], vis[j ^ 1], l[j].z);
        for (int j = 1; j <= c; ++j)
            if (i & (1 << (j - 1)))
                ++now, add(s, belong[j], inf), add(belong[j], s, 0);
        ans[now] = min(dinic(), ans[now]);
    }
    for (int i = 1; i <= c; ++i)
        printf("%d\n", ans[i]);
}