发布时间：2024-03-22

SCOI2011/BZOJ2330 糖果/银河

在差分约束中提到本题跑最长路求最小值，当时使用的是spfa，但是数据大一点就会被卡，本题可以使用tarjan算法线性求解

第一步是缩点
第二步判断正环：因为所有边权大于等于0，因此在一个强连通分量中只要有一条边大于0则有正环；如果没有正环，那么当前强连通分量的边均为0
第三步拓扑序求最长路即可

cpp

int dfn[N],low[N],in_st[N],id[N],idx,scc_cnt;
vector<array<int,2>> adj[N],g[N];
stack<int> st;
int dis[N],siz[N];
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    st.push(u);
    in_st[u]=1;
    for(auto [v,c]:adj[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_st[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++scc_cnt;
        int y;
        do{
            y=st.top();
            st.pop();
            in_st[y]=0;
            id[y]=scc_cnt;    
            siz[scc_cnt]++;        
        }while(y!=u);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    while(m--){
        int x,a,b;
        cin>>x>>a>>b;
        if(x==1)adj[a].push_back({b,0}),adj[b].push_back({a,0});
        else if(x==2)adj[a].push_back({b,1});
        else if(x==3)adj[b].push_back({a,0});
        else if(x==4)adj[b].push_back({a,1});
        else adj[a].push_back({b,0});
    }
    for(int i=1;i<=n;i++)adj[0].push_back({i,1});
    tarjan(0);
    for(int u=0;u<=n;u++){
        for(auto [v,c]:adj[u]){
            int a=id[u],b=id[v];
            if(a==b){
                if(c>0){
                    cout<<"-1\n";
                    return;
                }
            }
            else g[a].push_back({b,c});
        }
    }
    for(int u=scc_cnt;u>=1;u--){
        for(auto [v,c]:g0[u]){
            dis[v]=max(dis[v],dis[u]+c);
        }
    }
    int res=0;
    for(int i=1;i<=scc;i++)res+=siz[i]*dis[i];
    cout<<res<<"\n";
}

强连通分量

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

题意：
求是否存在点，使其他点都可以到达他
思路：

缩点找出度为0的点
如果这样的点大于1个，那么答案为0
否则为那个点的大小

cpp

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp,scc_cnt;
int dout[N],id[N],siz[N];
int stk[N],top;
bool in_stack[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    in_stack[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        int y;
        scc_cnt++;
        do{
            y=stk[top--];
            in_stack[y]=0;
            id[y]=scc_cnt;
            siz[scc_cnt]++;
        }while(y!=u);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int u=1;u<=n;u++){
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(id[u]!=id[v]){
                dout[id[u]]++;
            }
        }
    }

    int zero=0,sum=0;
    for(int i=1;i<=scc_cnt;i++){
        if(!dout[i]){
            zero++;
            sum+=siz[i];
            if(zero>1){
                sum=0;
                break;
            }
        }
    }
    cout<<sum<<"\n";
}

P2746 [USACO5.3] 校园网Network of Schools

题意：
有向图加多少条边能成为强连通分量思路：

缩点之后，起点个数有p个，终点有q个，答案为max(p,q)，特判scc=1时答案为0
证明：p<=q
- p=1时，全部终点向起点连边即可，答案为q
- p>1时，
- 必然找到多组起点终点，让一组的终点与起点相连，会连p-1条边
- 此时变成了p=1的情况，剩下还有q-(p-1)个终点
- 根据p=1的情况，需要连q-p+1条边
- 一共q-p+1+p-1=q条边
- 因此总边数为q
- p>=q同理

cpp

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp,scc_cnt;
int dout[N],din[N],id[N];
int stk[N],top;
bool in_stack[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    in_stack[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        int y;
        scc_cnt++;
        do{
            y=stk[top--];
            in_stack[y]=0;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}
void solve(){
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int t;
        while(cin>>t,t)add(i,t);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int u=1;u<=n;u++){
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(id[u]!=id[v]){
                dout[id[u]]++;
                din[id[v]]++;
            }
        }
    }
    int p=0,q=0;
    for(int i=1;i<=scc_cnt;i++){
        if(!dout[i])q++;
        if(!din[i])p++;
    }

    cout<<p<<"\n";
    if(scc_cnt!=1)cout<<max(p,q)<<"\n";
    else cout<<"0\n";
}

无向图与双连通分量

边双连通分量：极大的不含桥的连通块
点双连通分量：极大的不含割点的连通块
每个割点至少属于两个连通分量
两个割点之间的边不一定是桥

P2860 [USACO06JAN] Redundant Paths G

题意：
给定一张无向图，问加多少条边能使图变成边双连通分量
思路：
假设缩点后度数为1的点为 $cnt$ 个，那么答案为 $\lceil \frac{cnt}{2} \rceil$

cpp

int n,m;
int h[N],e[M],ne[M],idx;
int stk[N],top,id[N],dfn[N],low[N],timestamp,dcc_cnt;
bool is_bridge[M];
int d[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]){
                is_bridge[i]=is_bridge[i^1]=1;
            }
        }
        else if(i!=(from^1)){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        int y;
        ++dcc_cnt;
        do{
            y=stk[top--];
            id[y]=dcc_cnt;
        }while(y!=u);
    }
}
void solve(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    tarjan(1,-1);
    for(int i=0;i<idx;i++){
        if(is_bridge[i]){
            d[id[e[i]]]++;
        }
    }
    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++){
        if(d[i]==1)cnt++;
    }
    cout<<(cnt+1)/2<<"\n";
}

点的双连通分量

求割点
- 如果不是根节点，必然是割点
- 如果是根节点，至少要有两个子节点

POJ2119电力

题意：
给定一张图，求去除一个点后的连通块最大值
思路：
将每个割点求出来删去判断即可

cpp

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root,ans;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    int cnt=0;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])cnt++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(u!=root&&cnt)cnt++;
    ans=max(ans,cnt);
}
void solve(){
    while(cin>>n>>m,n||m){
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        idx=timestamp=0;
        while(m--){
            int a,b;
            cin>>a>>b;
            add(a,b);
            add(b,a);
        }
        int cnt=0;
        ans=0;
        for(root=0;root<n;root++){
            if(!dfn[root]){
                cnt++;
                tarjan(root);
            }
        }
        cout<<ans+cnt-1<<"\n";
    }
}

P3225 [HNOI2012] 矿场搭建

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

思路

求点双连通分量

首先每个连通块单独考虑
然后缩点，看割点的数量
- 如果没有割点，那么至少需要2个出口(一个出口塌了还有另一个出口)，方案数为 $C_{cnt}^2$
- 否则将割点单独做一个点，跟他相连的双连通分量为另外的点(但是在加连通分量的点时仍然把割点加进去)；
- 如果割点数量为1，则需要加至少1个出口(除割点外的位置)，方案数为 $cnt-1$ $c n t - 1$
  - 证明：如果割点坍塌或除内部出口外的点，那么连通块走内部出口；如果内部出口坍塌，则一定能走到割点，从而走向另外的割点数量为1的点(实际上就是一颗树的叶子节点)
- 如果割点数量为>1，则不需要放置出口，一定能走出连通块走向叶子节点
- 注意：缩点之后割点的数量即点的度数

cpp

int dfn[N],low[N],dcc_cnt,timestamp;
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
vector<int> dcc[N],st;
bool cut[N];
int root;
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    st.push_back(u);
    if(u==root&&h[u]==-1){
        ++dcc_cnt;
        dcc[dcc_cnt].push_back(u);
        return;
    }
    int cnt=0;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                cnt++;
                if(u!=root||cnt>1)cut[u]=1;
                ++dcc_cnt;
                int y;
                do{
                    y=st.back();
                    st.pop_back();
                    dcc[dcc_cnt].push_back(y);
                }while(y!=v);
                dcc[dcc_cnt].push_back(u);   
            }
        }
        else low[u]=min(low[u],low[v]);
    }
}
void solve(){
    int T=1;
    int n,m;
    while(cin>>m,m){
        for(int i=1;i<=dcc_cnt;i++)dcc[i].clear();
        n=dcc_cnt=idx=times=0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        memset(cut,0,sizeof cut);
        for(int i=1;i<=m;i++){
            int a,b;
            cin>>a>>b;
            n=max({a,b,n});
            add(a,b);
            add(b,a);
        }
        for(root=1;root<=n;root++){
            if(!dfn[root])tarjan(root);
        }
        unsigned long long res=1,ans=0;
        for(int i=1;i<=dcc_cnt;i++){
            int cnt=0;
            for(auto it:dcc[i])cnt+=cut[it];
            if(cnt==0)res*=dcc[i].size()*(dcc[i].size()-1)/2,ans+=2;
            else if(cnt==1)res*=dcc[i].size()-1,ans++;
        }
        cout<<"Case "<<T++<<": "<<ans<<" "<<res<<"\n";
    }
}

SCOI2011/BZOJ2330 糖果/银河 ​

强连通分量 ​

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G ​

P2746 [USACO5.3] 校园网Network of Schools ​

无向图与双连通分量 ​

P2860 [USACO06JAN] Redundant Paths G ​

点的双连通分量 ​

POJ2119电力 ​

P3225 [HNOI2012] 矿场搭建 ​

思路 ​