【LG-P2472 [SCOI2007]】蜥蜴

· · 个人记录

传送门：P2472 [SCOI2007]蜥蜴

最大网络流（建图复杂）

此题外附一个当前弧优化的运用。

除建图外，其余都是 \text{Dinic} 板子了。

  1. 石柱内部建两个点，一个入口，一个出口， 容量为其高度；

  2. 如果可以一步跳出地图，就和汇点连一条边；

  3. 源点和木桩连边，因为一个木桩上只有一只蚂蚱，所以容量为 1；

  4. 若木桩 A 到木桩 B 能一步跳到，就在它们之间连边，容量为 \text{inf}。

代码 + 注释

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define maxn 25
#define maxm 100005//数组需开大 
#define inf 2147483647
int n, m, d, nm;
int c[maxn][maxn], cntc, l[maxm], r[maxm], ans;
int s, t, p[maxn][maxn], tot;
int dep[maxm];
int hd[maxm], cur[maxm], cnt = 1;
struct node{
    int to, nxt, w;
}e[maxm << 1];
struct animl{
    int lie, hng;
};
vector <animl> an;

inline void add(int u, int v, int w)
{
    e[++cnt].to = v;
    e[cnt].nxt = hd[u], e[cnt].w = w;
    hd[u] = cnt;
    e[++cnt].to = u;
    e[cnt].nxt = hd[v], hd[v] = cnt;
}

inline int dist(int x, int y, int a, int b)
{
    return (x - a) * (x - a) + (y - b) * (y - b);
}

inline bool bfs()
{
    queue <int> q;
    memset(dep, 0, sizeof dep);
    dep[s] = 1, q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v, i = hd[u]; i; i = e[i].nxt)
        {
            if(!dep[v = e[i].to] and e[i].w)
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }                              
        }
    }
    return dep[t] ? true : false;
}

inline int dinic(int u, int in)
{
    if(u == t or !in) return in;
    int out = 0;
    for(int v, &i = cur[u]/*cur[u] 随着 i 的变化而变化*/; i and in/*注意判容量剩余*/; i = e[i].nxt)
            /*当前弧优化*/ 
    {
        if(dep[v = e[i].to] == dep[u] + 1 and e[i].w)
        {
            int res = dinic(v, min(in, e[i].w));
            e[i].w -= res, e[i ^ 1].w += res;
            in -= res, out += res;
        }
    }
    if(!out) dep[u] = 0;
    return out;
}

int main()
{
    //输入 
    scanf("%d %d %d", &n, &m, &d);
    nm = n * m, t = nm * 2 + 1;
    rep(i, 1, n) rep(j, 1, m)
    {
        p[i][j] = ++tot;
        char ch;
        cin >> ch;
        c[i][j] = ch - 48;
        if(c[i][j]) l[++cntc] = i, r[cntc] = j;
    }
    rep(i, 1, n) rep(j, 1, m)
    {
        char ch;
        cin >> ch;
        if(ch == 'L')
            an.push_back((animl){j, i}/*注意顺序*/);
    }

    //建图： 
    rep(i, 1, cntc)
    {
        int L = l[i], R = r[i];
        add(p[L][R], p[L][R] + nm, c[L][R]);//1.石柱内部建两个点，一个入口，一个出口， 容量为其高度 
        if(L <= d or R <= d or L + d > n or R + d > m)
            add(p[L][R] + nm, t, inf);//2.如果可以一步跳出地图，就和汇点连一条边 
    }
    rep(i, 0, an.size() - 1)
        add(s, p[an[i].hng][an[i].lie], 1);//3.源点和木桩连边，因为一个木桩上只有一只蚂蚱，所以容量为 1 
    rep(i, 1, cntc) rep(j, 1, cntc)
    {
        if(d * d >= dist(l[i], r[i], l[j], r[j]) and i != j)
            add(p[l[i]][r[i]] + nm, p[l[j]][r[j]], inf);//4.木桩和木桩之间连边，容量为 Inf 
    }

    while(bfs())//Dinic板子 
    {
        rep(i, s, t) cur[i] = hd[i];//当前弧优化-数组初始化 
        ans += dinic(s, inf);
    }
    printf("%d\n", an.size() - ans);
    return 0; 
}

——End——