【BZOJ1565】【NOI2009】植物大战僵尸

题目

题目在这里

思路&做法

没什么好说的

应该很容易看出是 最大闭合子图 吧?

不过要注意一下的是,这题 可能有植物是不可能被击溃的 , 所以要先跑一遍 拓扑排序 把这些点排除掉

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 810, M = 500010;

const int INF = 0x7F7F7F7F;

int n, m;

int val[40][40];
vector< pair<int, int> > vec[40][40];

bool vis[N]; //vis为0的点就是不可能击溃的点

struct edge
{   int from, to, flow, cap;
    edge() { }
    edge(int _1, int _2, int _3, int _4) : from(_1), to(_2), flow(_3), cap(_4) { }
};

struct Dinic
{   edge edges[M];
    int head[N], nxt[M], tot;

    int L, R;

    inline void init()
    {   memset(head, -1, sizeof(head));
        tot = 0;
    }

    void add_edge(int x, int y, int z)
    {   edges[tot] = edge(x, y, 0, z);
        nxt[tot] = head[x];
        head[x] = tot++;
        edges[tot] = edge(y, x, 0, 0);
        nxt[tot] = head[y];
        head[y] = tot++;
    }

    int s, t;

    int d[N];

    bool bfs()
    {   memset(d, -1, sizeof(d));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        while (!q.empty())
        {   int x = q.front(); q.pop();
            for (int i = head[x]; ~i; i = nxt[i])
            {   edge & e = edges[i];
                if (vis[e.to] && e.cap > e.flow && d[e.to] == -1)
                {   d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return d[t] != -1;
    }

    int cur[N];

    int dfs(int x, int a)
    {   if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int & i = cur[x]; ~i; i = nxt[i])
        {   edge & e = edges[i];
            if (vis[e.to] && d[e.to] == d[x] + 1 && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0)
            {   e.flow += f;
                edges[i^1].flow -= f;
                a -= f;
                flow += f;
                if (!a) break;
            }
        }
        return flow;
    }

    int maxflow(int _s, int _t)
    {   s = _s, t = _t;
        int flow = 0;
        while (bfs())
        {   for (int i = L; i <= R; i++)
                cur[i] = head[i];
            flow += dfs(s, INF);
        }
        return flow;
    }
} dinic;

int S, T;

int in[N];

int num[N];

inline int id(int x, int y) { return (x-1)*m + y; }

void topo()
{   queue<int> q;
    for (int i = 1; i <= n*m; i++)
        if (!in[i]) q.push(i);
    while (!q.empty())
    {   int x = q.front(); q.pop();
        vis[x] = 1;
        for (int i = dinic.head[x]; ~i; i = dinic.nxt[i])
        {   edge & e = dinic.edges[i];
            if (e.to == S || e.to == T || in[e.to] == 0 || e.cap > e.flow)
                continue;
            if ((--in[e.to]) == 0)
                q.push(e.to);
        }
    }
}

void build()
{   S = n * m + 1, T = n * m + 2;
    dinic.init();
    dinic.L = 0, dinic.R = n * m + 2;
    for (int i = 1; i <= n; i++)
    {   for (int j = 1; j <= m; j++)
        {   if (val[i][j] > 0)
                dinic.add_edge(S, id(i, j), val[i][j]);
            if (val[i][j] < 0)
                dinic.add_edge(id(i, j), T, -val[i][j]);
            for (int k = 0; k < vec[i][j].size(); k++)
            {   dinic.add_edge(id(vec[i][j][k].first, vec[i][j][k].second), id(i, j), INF);
                in[id(vec[i][j][k].first, vec[i][j][k].second)]++;
            }
            if (j > 1)
                dinic.add_edge(id(i, j-1), id(i, j), INF),
                in[id(i, j-1)]++;
        }
    }
}

int main()
{   scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {   int l;
            scanf("%d %d", &val[i][j], &l);
            num[id(i, j)] = val[i][j];
            for (int k = 1; k <= l; k++)
            {   int x, y;
                scanf("%d %d", &x, &y);
                x++, y++;
                vec[i][j].push_back(make_pair(x, y));
            }
        }
    build();
    topo(); 
    int ans = 0;
    for (int i = 1; i <= n*m; i++)
        if (vis[i] && num[i] > 0)
            ans += num[i];
    vis[S] = vis[T] = 1;
    ans -= dinic.maxflow(S, T);
    printf("%d\n", ans);
    return 0;
}

发表于 2018-06-04 11:26:40 in 网络流--最小割