luogu題解 P2860[USACO備援路徑Redundant Paths] 縮點+橋

題目連結

https://www.luogu.org/problemnew/show/P2860

https://www.lydsy.com/JudgeOnline/problem.php?id=1718

分析

首先這題目的意思就是讓任意兩點之間至少有兩條沒有重複道路的路徑，很顯然，如果這個圖不存在橋，就一定滿足上述條件。

于是我們就是要求使這個圖不存在橋需要連接配接的最小邊數

如果把橋從圖中去掉，很顯然剩餘的聯通塊中任意兩點之間至少有兩條沒有重複道路的路徑（當然也可能不是聯通塊而是孤立的點），對答案不會産生貢獻，我們不妨就将這些聯通塊縮點，于是就原來的圖就變成了一顆樹。

然後思考題目要求，當每個節點的度為2時任意兩點之間至少有兩條沒有重複道路的路徑，因為此時任意節點都有兩條不同道路可走，于是用貪心的思想我們讓度數為\(1\)的先互相連接配接，是以計算出樹中的葉節點個數\(x\)，\(\lceil\frac{x}{2}\rceil\)就是答案

注意

好象沒什麼注意的，不過我太菜把\(edge [j] .to\)寫成\(edge [i] .to\)查了好久的錯

代碼

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <cmath>
    #include <map>
    #include <queue>
    #define ll long long 
    #define ri register int 
    using namespace std;
    const int maxn=5005;
    const int maxm=10005;
    const int inf=0x7fffffff;
    template <class T>inline void read(T &x){
        x=0;int ne=0;char c;
        while(!isdigit(c=getchar()))ne=c=='-';
        x=c-48;  
        while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
        x=ne?-x:x;
        return ;
    }
    struct Edge{
        int ne,to;
    }edge[maxm<<1];
    int h[maxn],num_edge=0;
    inline void add_edge(int f,int to){
        edge[++num_edge].ne=h[f];
        edge[num_edge].to=to;
        h[f]=num_edge;
        return ;
    }
    int n,m;
    int dfn[maxn],low[maxn],tot=0;
    bool bridge[maxm];
    void tarjan(int now,int in_edge){//所在邊的标号
        int v;dfn[now]=low[now]=++tot;
        for(ri i=h[now];i;i=edge[i].ne){
            v=edge[i].to;
            if(!dfn[v]){
                tarjan(v,i);
                low[now]=min(low[now],low[v]);
                if(dfn[now]<low[v]){
                   bridge[i]=bridge[i^1]=true;//是橋
                   bb++;
                }
            }
            else if(i!=(in_edge^1)){//如果不是在同一條無向邊的對應邊
                low[now]=min(low[now],dfn[v]);
            }
        }
        return ;
    }
    int num=0;//聯通塊的數量
    int in_block[maxn];//各點所在聯通塊的标号
    bool g[maxn][maxn];//重構後的圖（儲存）
    void Contraction_Point(int now){//縮點
        int v;in_block[now]=num;
        for(ri i=h[now];i;i=edge[i].ne){
           v=edge[i].to;
           if(!bridge[i]&&!in_block[v]){
               Contraction_Point(v);
           }
        }
        return ;
    }
    int du[maxn];
    inline void solve(){
        int ans=0,x,y;
        memset(g,0,sizeof(g));
        for(ri i=1;i<=n;i++){
            x=in_block[i];
            for(ri j=h[i];j;j=edge[j].ne){
                y=in_block[edge[j].to];    //太坑了
                g[x][y]=g[y][x]=1;
            }
        }
        memset(du,0,sizeof(du));
        for(ri i=1;i<=num;i++){
            for(ri j=1;j<=num;j++){
                if(i!=j&&g[i][j]){du[j]++;
                }
            }
        }
        for(ri i=1;i<=num;i++){
            if(du[i]==1)ans++;
        }
        printf("%d",(int)ceil(ans/double(2)));
        return ;
    }
    int main(){
        int x,y;
        read(n),read(m);
        num_edge=1;
        for(ri i=1;i<=m;i++){
            read(x),read(y);
            add_edge(x,y);
            add_edge(y,x);
        }
        memset(bridge,0,sizeof(bridge));
        tarjan(1,0);
        memset(in_block,0,sizeof(in_block));
        for(ri i=1;i<=n;i++){
            if(!in_block[i]){
                num++;
                Contraction_Point(i);
            }
        }
        solve();
        return 0;
    }
    
           

轉載于:https://www.cnblogs.com/Rye-Catcher/p/9286688.html