P2738 [USACO4.1]篱笆回路Fence Loops

· · 题解

P2738 [USACO4.1]篱笆回路Fence Loops

这个题的难点主要在于建图, 只要图建好了, 找一下最小环就好。所以我们主要考虑怎么建图。

注意到这题的输入是按边来输入的, 所以我们可以先假定编号为 i 一条边的两个端点是是 2i - 1 和 2i 并且规定 2i - 1 是其输入时的第一个端点。那么我们就分别存一下两个端点与哪些边相交, 然后枚举 i 和 j, 判断 i 的哪个端点与 j 的哪个端点是同一个端点, 然后去重即可。

那如何去重呢？注意到两个点相同这样的信息可以使用并查集维护, 于是我们可以在枚举发现两个端点相同时将这两个端点所在的集合合并, 最后给剩下的每个根节点重新编号, 然后每条边的两个端点改成其所在集合的根节点的编号即可。

图建完了之后就剩下跑最小环了, 可以用Floyd来算, 不过由于我Floyd的方法不知道为什么写炸了, 所以我就改成枚举每条边, 然后对每条边从一个端点出发跑 SPFA (不过这里要注意一下, 跑 SPFA 时要特判走的边是否就是枚举的这条边)再加上这条边的长度就好。

复杂度大概在 O(n^{2}) 左右。

下面是我的Code:


#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2e2 + 5;
int n, x, y, z, l, r, cur, cure, cant;
int fa[maxn], dy[maxn], head[maxn], nex[maxn], to[maxn], val[maxn], dis[maxn];
bool al[maxn];
queue<int> q;
struct node{ //存每条边的信息 
    int u, v, w;
    bool ltmp[maxn], rtmp[maxn];
}ep[maxn];
void init(){ // 并查集初始化 
    for(int i = 0;i < maxn;i++){
        fa[i] = i;
    }
    return ;
}
int find(int x){ // 找一个集合根节点 
    if(fa[x] == x){
        return x;
    }
    return fa[x] = find(fa[x]);
}
void merge(int x, int y){ // 合并两个集合 
    fa[find(x)] = find(y);
    return ;
}
void add(int u, int v, int w){ // 链式前向星 
    nex[++cure] = head[u];
    to[cure] = v;
    val[cure] = w;
    head[u] = cure;
    return ;
}
void spfa(int s){ // SPFA 
    memset(dis, 0x3f, sizeof(dis));
    memset(al, 0, sizeof(al));
    q.push(s);
    dis[s] = 0;
    al[s] = 1;
    while(!q.empty()){
        int fr = q.front();
        q.pop();
        al[fr] = 0;
        for(int i = head[fr];i;i = nex[i]){
            int t = to[i];
            int k = val[i];
            if(dis[fr] + k < dis[t]){
                if(i == cant || i == cant + 1){ // 这里的 cant 就是不能走的边的编号
                    continue;                   // 由于是无向图，所以cant + 1就是其反向边 
                }
                dis[t] = dis[fr] + k;                           
                if(al[t]){
                    continue;
                }
                q.push(t);
                al[t] = 1;
            }
        }
    }
    return ;
}
int main(){
    init();
    scanf("%d", &n);
    for(int i = 1;i <= n;i++){
        scanf("%d %d %d %d", &x, &z, &l, &r); // 输入 
        ep[x].u = 2 * x - 1;
        ep[x].v = 2 * x;
        ep[x].w = z;
        for(int j = 1;j <= l;j++){
            scanf("%d", &y);
            ep[x].ltmp[y] = 1; // 记录与那些边相交 
        }
        for(int j = 1;j <= r;j++){
            scanf("%d", &y);
            ep[x].rtmp[y] = 1;
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i == j){
                continue;
            }
            if(ep[i].ltmp[j] && ep[j].ltmp[i]){
                merge(ep[i].u, ep[j].u);        // 并查集维护 
            }
            if(ep[i].ltmp[j] && ep[j].rtmp[i]){
                merge(ep[i].u, ep[j].v);
            }
            if(ep[i].rtmp[j] && ep[j].ltmp[i]){
                merge(ep[i].v, ep[j].u);
            }
            if(ep[i].rtmp[j] && ep[j].rtmp[i]){
                merge(ep[i].v, ep[j].v);
            }
        }
    }
    for(int i = 1;i <= 2 * n;i++){
        if(fa[i] == i){
            dy[fa[i]] = ++cur; // 给剩下的集合根节点重新编号 
        }
    }
    for(int i = 1;i <= n;i++){
        ep[i].u = dy[find(ep[i].u)]; // 去重 
        ep[i].v = dy[find(ep[i].v)];
        add(ep[i].u, ep[i].v, ep[i].w); // 加边 
        add(ep[i].v, ep[i].u, ep[i].w);
    }
    int ans = 0x3f3f3f3f;
    for(int i = 1;i <= cure;i += 2){ // 由于 i + 1 就是其反向边所以没有必要再枚举一次, 让其直接跳过 
        int j = (i + 1) / 2;
        cant = i; // 记录不能走的边的编号 
        spfa(ep[j].v); // 从一个端点跑 SPFA 
        ans = min(ans, ep[j].w + dis[ep[j].u]); // 更新答案 
    }
    printf("%d", ans); // 输出 
    return 0;
}