题解：P12744 [POI 2016 R3] 树篱 Hedge

yaochenchen · 2026-04-28 11:35:01 · 题解

前言

水题，竟然没人写题解qwq。

题意

• 有一个 m \times n 的网格（n 为奇数），顶点数为 V = m \cdot n。
• 相邻格子之间有一条边，边的总数为 E = m(n-1) + (m-1)n。
• 每条边有两种类型：可种杜松（C）或只能种侧柏（T）。
• 北墙正中与南墙正中各有一个入口，分别连接到 (0, \lfloor n/2 \rfloor) 和 (m-1, \lfloor n/2 \rfloor)（入口边固定存在且不可种树篱）。
• 选择一些边种上树篱（即障碍），使得未种树篱的边（连同两条入口边）构成一棵树（连通且无环）。等价于：在内部边中选择一个生成树 T（包含 V-1 条边），剩余边 E \setminus T 即为树篱。
• 树篱段数固定为 |E| - (V-1)。
• 杜松树篱段数 = 总 C 边数 |E_C| 减去生成树 T 中包含的 C 边数。
• 目标：最大化杜松树篱段数 \iff 最小化生成树中 C 边的数量。

思路

用 Kruskal 优先加入所有 T 边，再用 C 边补全生成树。这样得到的生成树中 C 边数最少，从而树篱中 C 边数（杜松树篱）最大。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int qr() {
    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 f*x;
}
const int maxn=1005;
int m,n;
int totC, totE, V;
int cntC_tree;

struct DSU {
    int fa[maxn*maxn], sz[maxn*maxn];
    void init(int n) {
        for (int i=0;i<n;i++) fa[i]=i, sz[i]=1;
    }
    int find(int x) {
        while (fa[x]!=x) fa[x]=fa[fa[x]], x=fa[x];
        return x;
    }
    bool unite(int x, int y) {
        x=find(x), y=find(y);
        if (x==y) return 0;
        if (sz[x]<sz[y]) swap(x,y);
        fa[y]=x; sz[x]+=sz[y];
        return 1;
    }
} dsu;

struct Edge {
    int u, v, id;
};
vector<Edge> Tedge, Cedge;
vector<bool> in_tree;
int id_cnt;

void add_edge(int u, int v, char ch) {
    if (ch=='C') {
        Cedge.push_back({u,v,id_cnt});
        totC++;
    } else {
        Tedge.push_back({u,v,id_cnt});
    }
    id_cnt++;
}

signed main() {
    m=qr(); n=qr();
    V=m*n;
    string s;
    for (int i=0;i<m;i++) {
        cin>>s;
        for (int j=0;j<n-1;j++) {
            int u=i*n+j, v=i*n+j+1;
            add_edge(u,v,s[j]);
        }
    }
    for (int i=0;i<m-1;i++) {
        cin>>s;
        for (int j=0;j<n;j++) {
            int u=i*n+j, v=(i+1)*n+j;
            add_edge(u,v,s[j]);
        }
    }
    totE = id_cnt;
    in_tree.assign(totE, false);
    dsu.init(V);
    for (auto &e : Tedge) {
        if (dsu.unite(e.u, e.v)) in_tree[e.id]=true;
    }
    for (auto &e : Cedge) {
        if (dsu.unite(e.u, e.v)) {
            in_tree[e.id]=true;
            cntC_tree++;
        }
    }
    int hedge = totE - (V-1);
    int jun = totC - cntC_tree;
    cout<<hedge<<' '<<jun<<'\n';
    int id=0;
    for (int i=0;i<m;i++) {
        for (int j=0;j<n-1;j++) {
            cout<<(in_tree[id++] ? '.' : 'Z');
        }
        cout<<'\n';
    }
    for (int i=0;i<m-1;i++) {
        for (int j=0;j<n;j++) {
            cout<<(in_tree[id++] ? '.' : 'Z');
        }
        cout<<'\n';
    }
    return 0;
}