您现在的位置是:首页 > 正文

【图论】有向图的强连通分量

2024-02-29 13:31:26阅读 0

有向图的强连通分量

连通分量: 对于分量中任意两点 u , v u,v u,v,必然可以从 u u u走到 v v v,且从 v v v走到 u u u
强连通分量( S C C SCC SCC): 极大连通分量。一个连通分量加上任何一些点都不是连通分量了,该连通分量就是强连通分量。
强连通分量的作用: 将任意有向图通过 缩点(将所有连通分量缩成一个点) 转换成有向无环图( D A G DAG DAG)。
在这里插入图片描述
常见应用:对于上图,将有向图缩点之后,可以直接按照拓扑序递推来求最短路/最长路

如何求强连通分量( T a r j a n Tarjan Tarjan算法)

D F S DFS DFS
一些概念:
边可以分为四大类:
1.树枝边 ( x , y ) (x,y) (x,y) x x x y y y的父节点
在这里插入图片描述

2.前向边( x x x, y y y)。 x x x y y y的祖先节点
在这里插入图片描述
3.后向边( x x x, y y y)
在这里插入图片描述
4.横叉边(往之前搜过的其他分支搜,连向其他分支的边)
在这里插入图片描述
如果一个点在强连通分量( S C C SCC SCC)中
情况1:存在一条后向边,指向祖先结点
情况2:先走到横叉边,横叉边再走到祖先节点

Tarjan算法求强连通分量( S C C SCC SCC)
引入时间戳的概念,在搜索的时候给每一个点一个编号(按照深度优先搜索的顺序)
在这里插入图片描述
对每个点定义两个时间戳:
d f n [ u ] dfn[u] dfn[u]表示遍历到 u u u的时间戳
l o w [ u ] low[u] low[u]表示从 u u u开始走,所能遍历到的最小的时间戳
u u u是其所在的强连通分量的最高点,等价于 d f n [ u ] dfn[u] dfn[u]== l o w [ u ] low[u] low[u]
tarjan算法模板

void tarjan(int u){
    //dfn是当前点的时间戳,low是该点能够到达的最小的时间戳
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;//将当前点加入栈当中
    for(int i=head[u];~i;i=ne[i]){//遍历u所有能到的点
        int v=e[i];
        if(!dfn[v]){//如果该点还没有被遍历过
            tarjan(v);
            low[u]=min(low[u],low[v]);//更新最小的时间戳
        }
        else if(in_stk[v])low[u]=min(low[u],dfn[v]);//如果v点还在栈中,就用这个点来更新low值
    }
    if(dfn[u]==low[u]){//u是该强连通分量的最高点
        ++scc_cnt;
        int y;
        do{
            y=stk.top();stk.pop();//将该强连通分量的所有点出栈
            in_stk[y]=false;//不在栈中了
            id[y]=scc_cnt;//标记该点的强连通分量的下标
            Size[scc_cnt]++;//该连通分量的大小加1
        }while(y!=u);
    }
}

时间复杂度 O ( n + m ) O(n+m) O(n+m)

//缩点
for i=1;i<=n;i++
 for i的所有邻点j
   if i和j不在同一scc中:
    加一条新边id[i]→id[j]

形成一个有向无环图 ( D A G ) (DAG) (DAG)
缩点之后,强连通分量编号点按编号递减的顺序就是拓扑序。
假设对于一个点 u u u,当我们执行if(dfn[u]==low[u])这句话时,说明 u u u点所能到的点都搜完了,也就是这个点的所有后继都搜完了,我们才将这个点所在序列当中(也就是标记为 s c c _ c n t scc\_cnt scc_cnt),逆序来看的话,所有这个点的后继都在这个点的前面,那必然就是拓扑序了。

受欢迎的牛

原题链接
每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 N N N头牛,编号从 1 1 1 N N N,给你 M M M对整数 ( A , B ) (A,B) (A,B),表示牛 A A A认为牛 B B B受欢迎。
这种关系是具有传递性的,如果 A A A认为 B B B受欢迎, B B B认为 C C C受欢迎,那么牛 A A A也认为牛 C C C受欢迎。
你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

输入格式
第一行两个数 N , M N,M N,M
接下来 M M M行,每行两个数 A , B A,B A,B,意思是 A A A认为 B B B是受欢迎的(给出的信息有可能重复,即有可能出现多个 A , B A,B A,B)。

输出格式
输出被除自己之外的所有牛认为是受欢迎的牛的数量。

数据范围
1 ≤ N ≤ 1 0 4 1≤N≤10^4 1N104,
1 ≤ M ≤ 5 × 1 0 4 1≤M≤5×10^4 1M5×104

输入样例:

3 3
1 2
2 1
2 3

输出样例:

1

样例解释
只有第三头牛被除自己之外的所有牛认为是受欢迎的。

分析:
题目意思就是需要找到的牛是能够被其他所有牛所能到达的,直接暴力的话时间复杂度太大。
如果用拓扑图来说,这个题会变得简单,如果当前图是一个拓扑图,如果至少存在两个终点(没有出边,出度为 0 0 0),那么这两个终点不可达,那么答案为 0 0 0;如果只有一个点出度为 0 0 0,那么所有点都能走到这个点。所以对于拓扑图,我们只需要判断有几个出度为 0 0 0的点即可。那么本题,我们将一个图的强连通分量缩点成拓扑图,再进行判断。

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10005,M=50005;
int n,m;
int head[N],e[M],ne[M],tot;
int dfn[N],low[N],timestamp;
stack<int>stk;
bool in_stk[N];
int id[N],scc_cnt,Size[N];
int dout[N];
void add(int a,int b){
    e[tot]=b,ne[tot]=head[a],head[a]=tot++;
}
void tarjan(int u){
    //dfn是当前点的时间戳,low是该点能够到达的最小的时间戳
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;
    for(int i=head[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){//如果该点还没有被遍历过
            tarjan(v);
            low[u]=min(low[u],low[v]);//更新最小的时间戳
        }
        else if(in_stk[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){//u是该连通分量的最上面的点
        ++scc_cnt;
        int y;
        do{
            y=stk.top();stk.pop();//将该连通分量的所有点出栈
            in_stk[y]=false;//不在栈中了
            id[y]=scc_cnt;//标记该点的连通分量的下标
            Size[scc_cnt]++;//该连通分量的大小加1
        }while(y!=u);
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    memset(head,-1,sizeof(head));
    while(m--){
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])
            tarjan(i);//缩点
    }
    for(int i=1;i<=n;i++){
        for(int j=head[i];~j;j=ne[j]){
            int k=e[j];
            int a=id[i],b=id[k];//遍历每两个点,如果这两个点不在一个连通分量中,出度加1,相当于缩点了
            if(a!=b)dout[a]++;
        }
    }
    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++){
        if(!dout[i]){//出度为0的点只能有一个,最后的结果就是出度为0的那个连通分量的大小
            zeros++;
            sum+=Size[i];
            if(zeros>1){
                sum=0;
                break;
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}

学校网络

原题链接
一些学校连接在一个计算机网络上,学校之间存在软件支援协议,每个学校都有它应支援的学校名单(学校 A A A支援学校 B B B,并不表示学校 B B B一定要支援学校 A A A)。
当某校获得一个新软件时,无论是直接获得还是通过网络获得,该校都应立即将这个软件通过网络传送给它应支援的学校。
因此,一个新软件若想让所有学校都能使用,只需将其提供给一些学校即可。
现在请问最少需要将一个新软件直接提供给多少个学校,才能使软件能够通过网络被传送到所有学校?
最少需要添加几条新的支援关系,使得将一个新软件提供给任何一个学校,其他所有学校就都可以通过网络获得该软件?

输入格式
1 1 1行包含整数 N N N,表示学校数量。
2.. N + 1 2..N+1 2..N+1行,每行包含一个或多个整数,第 i + 1 i+1 i+1行表示学校 i i i应该支援的学校名单,每行最后都有一个 0 0 0表示名单结束(只有一个 0 0 0即表示该学校没有需要支援的学校)。

输出格式
输出两个问题的结果,每个结果占一行。

数据范围
2 ≤ N ≤ 100 2≤N≤100 2N100

输入样例:

5
2 4 3 0
4 5 0
0
0
1 0

输出样例:

1
2

分析:
假设有 P P P个起点, Q Q Q个终点
问题1: 只要把软件交给所有起点,软件就能够通过网络被传送到所有学校。因为所有的起点都无法由别的点走到,因此每个起点都必须分配一个软件,对于其他的点,一直往前找它的前驱,一定能够找到某个起点,所以从每个起点出发,一定能够走完整个图。所以将软件交给所有起点即可,答案就是 P P P
问题2: 加多少条边,使得整个图变成一个强连通分量,最少加 m a x ( P , Q ) max(P,Q) max(P,Q)个边。
不妨设 ∣ P ∣ ≤ ∣ Q ∣ |P| \leq |Q| PQ
1. ∣ P ∣ = = 1 |P|==1 P==1
每一个终点都可以被起点走到,每一个终点向起点连接一条边即可。
在这里插入图片描述
因为只要终点可以走到起点,中间点都能走到某个终点,起点又可以走到任何点,所以对于任何点都能走到所有点
2. ∣ P ∣ > 1 |P|>1 P>1 ∣ Q ∣ ≥ ∣ P ∣ > 1 |Q| \geq |P|>1 QP>1
在这里插入图片描述
假如这种情况, ∣ P ∣ = 2 |P|=2 P=2 ∣ Q ∣ = 2 |Q|=2 Q=2,那么每一个起点肯定对应一个终点,如果将其中一个终点连向起点,将 q 1 q_{1} q1连向 p 2 p_{2} p2 ∣ P ′ ∣ = P − { p 2 } |P'|=P-\{p_{2}\} P=P{p2}, ∣ Q ′ ∣ = Q − { q 1 } |Q'|=Q-\{q_{1}\} Q=Q{q1}
加一条边
新的 ∣ P ′ ∣ = ∣ P ∣ − 1 |P'|=|P|-1 P=P1, ∣ Q ′ ∣ = ∣ Q ∣ − 1 |Q'|=|Q|-1 Q=Q1
按照这样的方式 ∣ P − 1 ∣ |P-1| P1 次, ∣ P ∣ = 1 |P|=1 P=1 ∣ Q ′ ∣ = ∣ Q ∣ − ( ∣ P ∣ − 1 ) |Q'|=|Q|-(|P|-1) Q=Q(P1)
根据情况1可知
总共需要加的边数为 ∣ Q ∣ − ( ∣ P ∣ − 1 ) + ∣ P − 1 ∣ = ∣ Q ∣ |Q|-(|P|-1)+|P-1|=|Q| Q(P1)+P1=Q
3. ∣ P ∣ ≥ ∣ Q ∣ |P| \geq |Q| PQ同理

#include <bits/stdc++.h>
using namespace std;
const int N=105,M=N*N;
int n;
int e[M],ne[M],head[N],tot;
int dfn[N],low[N],timestamp;
stack<int>stk;
bool in_stk[N];
int id[N],scc_cnt;
int din[N],dout[N];
void add(int a,int b){
    e[tot]=b,ne[tot]=head[a],head[a]=tot++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=1;
    for(int i=head[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stk[v])//如果当前点已经遍历过了而且还在堆栈中
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){//计算出每一个连通分量
        ++scc_cnt;
        int y;
        do{
            y=stk.top();stk.pop();
            in_stk[y]=0;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}
int main()
{
    scanf("%d",&n);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++){
        int t;
        while(scanf("%d",&t)&&t)add(i,t);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=head[i];~j;j=ne[j]){
            int v=e[j];
            int a=id[i],b=id[v];
            if(a!=b){
                dout[a]++;
                din[b]++;
            }
        }
    }
    int a=0,b=0;
    for(int i=1;i<=scc_cnt;i++){//计算出有多少个起点和终点
        if(!din[i])a++;
        if(!dout[i])b++;
    }
    printf("%d\n",a);
    if(scc_cnt==1)puts("0");//如果只有一个强连通分量
    else printf("%d\n",max(a,b));
    return 0;
}

最大半连通子图

原题链接
一个有向图 G = ( V , E ) G=(V,E) G=(V,E)称为半连通的 (Semi-Connected),如果满足: ∀ u , v ∈ V ∀u,v∈V u,vV,满足 u → v u→v uv v → u v→u vu,即对于图中任意两点 u , v u,v u,v,存在一条 u u u v v v的有向路径或者从 v v v u u u的有向路径。
G ′ = ( V ′ , E ′ ) G′=(V′,E′) G=(V,E) 满足, E ′ E′ E E E E中所有和 V ′ V′ V有关的边,则称 G ′ G′ G G G G的一个导出子图。
G ′ G′ G G G G的导出子图,且 G ′ G′ G半连通,则称 G ′ G′ G G G G的半连通子图。
G ′ G′ G G G G所有半连通子图中包含节点数最多的,则称 G ′ G′ G G G G的最大半连通子图。
给定一个有向图 G G G,请求出 G G G的最大半连通子图拥有的节点数 K K K,以及不同的最大半连通子图的数目 C C C
由于 C C C可能比较大,仅要求输出 C C C X X X的余数。

输入格式
第一行包含三个整数 N , M , X N,M,X N,M,X N , M N,M N,M分别表示图 G G G的点数与边数, X X X的意义如上文所述;
接下来 M M M行,每行两个正整数 a , b a,b a,b,表示一条有向边 ( a , b ) (a,b) (a,b)
图中的每个点将编号为 1 1 1 N N N,保证输入中同一个 ( a , b ) (a,b) (a,b) 不会出现两次。

输出格式
应包含两行。
第一行包含一个整数 K K K,第二行包含整数 C m o d X C mod X CmodX

数据范围
1 ≤ N ≤ 1 0 5 , 1 ≤ M ≤ 1 0 6 , 1 ≤ X ≤ 1 0 8 1≤N≤10^5, 1≤M≤10^6, 1≤X≤10^8 1N105,1M106,1X108

输入样例:

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

输出样例:

3
3

分析:
半连通子图: 对于图中任意两点,要么 u − > v u->v u>v,要么 v − > u v->u v>u。即对于图中任意两点 u , v u,v u,v,存在一条 u u u v v v的有向路径或者从 v v v u u u的有向路径。
强连通分量必定是半连通分量
求最大半连通子图,最大半连通子图是所有半连通子图中,所含结点最多的子图
所以我们缩点(对强连通分量缩点,强连通分量必定是半连通分量)之后,所形成的一条链,求出来最长的链,链上的点的权值就是每个点所包含的节点数(缩点之后的强连通分量里面可能包含很多点),就是最大半连通子图,求数目递推的方式来求即可,动态规划。
1. t a r j a n tarjan tarjan算法
2.缩点,建图,给边判重
3.按拓扑序递推

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005,M=2000005;
int n,m,mod;
int head[N],hs[N],e[M],ne[M],tot;
int dfn[N],low[N],timestamp;
stack<int>stk;
bool in_stk[N];
int id[N],scc_cnt,scc_size[N];
int f[N],g[N];
void add(int h[],int a,int b){
    e[tot]=b,ne[tot]=h[a],h[a]=tot++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk.push(u);in_stk[u]=1;
    for(int i=head[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stk[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){//u是该强连通分量的最上面的结点
        ++scc_cnt;
        int y;
        do{
            y=stk.top();stk.pop();
            in_stk[y]=false;
            id[y]=scc_cnt;
            scc_size[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(hs,-1,sizeof(hs));
    scanf("%d %d %d",&n,&m,&mod);
    while(m--){
        int a,b;
        scanf("%d %d",&a,&b);
        add(head,a,b);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    unordered_set<ll>s;//(u,v)->u*100000+v;判重
    for(int i=1;i<=n;i++){
        for(int j=head[i];~j;j=ne[j]){
            int v=e[j];
            int a=id[i],b=id[v];
            ll hash=a*1000000ll+b;
            if(a!=b&&!s.count(hash)){
                add(hs,a,b);
                s.insert(hash);
            }
        }
    }

    for(int i=scc_cnt;i>=1;i--){//求出来的强连通分量的逆序就是我们的拓扑序
        if(!f[i]){//起点
            f[i]=scc_size[i];//节点数
            g[i]=1;//方案数
        }
        for(int j=hs[i];~j;j=ne[j]){
            int v=e[j];
            if(f[v]<f[i]+scc_size[v]){                    
                f[v]=f[i]+scc_size[v];
                g[v]=g[i];
            }
            else if(f[v]==f[i]+scc_size[v]){//节点数相同
                g[v]=(g[v]+g[i])%mod;
            }
        }
    }


    int maxf=0,sum=0;
    for(int i=1;i<=scc_cnt;i++){//求出来最大的结点数
        if(f[i]>maxf){
            maxf=f[i];
            sum=g[i];
        }
        else if(f[i]==maxf)sum=(sum+g[i])%mod;
    }
    printf("%d\n%d\n",maxf,sum);
    return 0;
}

银河

原题链接
银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。
我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是 1 1 1
现在对于 N N N颗我们关注的恒星,有 M M M对亮度之间的相对关系已经判明。
你的任务就是求出这 N N N颗恒星的亮度值总和至少有多大。

输入格式
第一行给出两个整数 N N N M M M
之后 M M M行,每行三个整数 T , A , B T,A,B T,A,B,表示一对恒星 ( A , B ) (A,B) (A,B)之间的亮度关系。恒星的编号从 1 1 1开始。
如果 T = 1 T=1 T=1,说明 A A A B B B亮度相等。
如果 T = 2 T=2 T=2,说明 A A A的亮度小于 B B B的亮度。
如果 T = 3 T=3 T=3,说明 A A A的亮度不小于 B B B的亮度。
如果 T = 4 T=4 T=4,说明 A A A的亮度大于 B B B的亮度。
如果 T = 5 T=5 T=5,说明 A A A的亮度不大于 B B B的亮度。

输出格式
输出一个整数表示结果。
若无解,则输出 − 1 −1 1

数据范围
N ≤ 100000 , M ≤ 100000 N≤100000,M≤100000 N100000,M100000

输入样例:

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

输出样例:

11

分析:
T = 1 : A = B ⇒ A ≥ B , B ≥ A 即 B + 0 → A , A + 0 → B T=1: A=B \Rightarrow A≥B,B≥A 即B+0 \rightarrow A ,A+0 \rightarrow B T=1:A=BAB,BAB+0A,A+0B
T = 2 : A < B ⇒ B ≥ A + 1 即 A + 1 → B T=2: A<B \Rightarrow B≥A+1 即A+1 \rightarrow B T=2:A<BBA+1A+1B
T = 3 : A ≥ B ⇒ A ≥ B 即 B + 0 → A T=3: A≥B \Rightarrow A≥B即B+0 \rightarrow A T=3:ABABB+0A
T = 4 : A > B ⇒ A ≥ B + 1 即 B + 1 → A T=4: A>B \Rightarrow A≥B+1即B+1 \rightarrow A T=4:A>BAB+1B+1A
T = 5 : A ≤ B ⇒ B ≥ A 即 A + 0 → B T=5: A≤B \Rightarrow B≥A即A+0 \rightarrow B T=5:ABBAA+0B
这个题也可以用差分约束来写
s p f a spfa spfa最长路 - 做完后每个点的距离就是最小值
边是非负数的,如果存在正环则无解
如果有解
1.必须要有绝对值
2.超级源点(能到所有点的点)
s p f a spfa spfa可能超时的
这次我们使用强连通分量来做
这个图的边权都 ≥ 0 \geq 0 0,判断是否存在正环,可以先把所有的强连通分量找出来,每一个环必定是在强连通分量之中的,如果环中有一条边的权值严格 > 0 >0 >0,那么就形成了一个正环。所以不存在正环,强连通分量中的边权都为0,每一个强连通分量中的点的最终距离都是相等的。
t a r j a n tarjan tarjan+缩点+拓扑序递推求最长路

代码:
t a r j a n tarjan tarjan+缩点+拓扑序递推求最长路

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005,M=400005;
int n,m;
int h[N],hs[N],e[M],ne[M],w[M],tot;
int dfn[N],low[N],timestamp;
stack<int>stk;
bool in_stk[N];
int id[N],scc_cnt,scc_size[N];
int dist[N];
void add(int h[],int a,int b,int c){
    e[tot]=b,w[tot]=c,ne[tot]=h[a],h[a]=tot++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk.push(u);in_stk[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_stk[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){//该点是该强连通分量的顶点
        ++scc_cnt;
        int y;
        do{
            y=stk.top();stk.pop();
            in_stk[y]=false;
            id[y]=scc_cnt;
            scc_size[scc_cnt]++;
        }while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof(h));
    memset(hs,-1,sizeof(hs));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)add(h,0,i,1);//虚拟源点到每一个点的权值都是1,因为每个点的亮度都大于等于1
    while(m--){
        int t,a,b;
        scanf("%d %d %d",&t,&a,&b);
        if(t==1)add(h,a,b,0),add(h,b,a,0);
        else if(t==2)add(h,a,b,1);
        else if(t==3)add(h,b,a,0);
        else if(t==4)add(h,b,a,1);
        else if(t==5)add(h,a,b,0);
    }
    tarjan(0);//这里只需要跑一个tarjan,因为如果存在孤立点,那么该孤立点的id就是0,只有0会和该孤立点相连,并且有权值,所以会直接不成立
    bool success=true;
    for(int i=0;i<=n;i++){
        for(int j=h[i];~j;j=ne[j]){
            int v=e[j];
            int a=id[i],b=id[v];
            if(a==b){//两者在同一个连通分量中
            // 也就是说,如果有环,要成立的话,那么环里面的权值必定为0。也就是说强连通分量中的每一个结点的值都是相等的
                if(w[j]>0){//如果边权不为0,而且这两个点在一个强连通分量中,说明有环存在,所以肯定无解
                    success=false;
                    break;
                }
            }
            else add(hs,a,b,w[j]);
        }
        if(!success)break;
    }
    if(!success)puts("-1");
    else{
        for(int i=scc_cnt;i;i--){//强连通分量的逆序就是拓扑序
            for(int j=hs[i];~j;j=ne[j]){
                int v=e[j];
                dist[v]=max(dist[v],dist[i]+w[j]);//按照拓扑序逐一计算最大的dist值
            }
        }
        ll res=0;
        for(int i=1;i<=scc_cnt;i++)res+=(ll)dist[i]*scc_size[i];//当前的强连通分量的边权乘以强连通分量中的点数
        printf("%lld\n",res);
    }
    return 0;
}

差分约束

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=3e5+5;
int n,k;
int head[N],e[M],ne[M],w[M],tot;
ll dis[N];
int vis[N],cnt[N];
void add(int u,int v,int d){
    e[tot]=v,w[tot]=d,ne[tot]=head[u],head[u]=tot++;
}
bool spfa(){
    stack<int>p;
    p.push(0);
    vis[0]=1;
    while(!p.empty()){
        int u=p.top();p.pop();
        vis[u]=0;
        for(int i=head[u];~i;i=ne[i]){
            int v=e[i];
            if(dis[v]<dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n+1)return true;
                if(!vis[v])p.push(v),vis[v]=1;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d %d",&n,&k);
    memset(head,-1,sizeof(head));
    while(k--){
        int x,a,b;scanf("%d %d %d",&x,&a,&b);
        if(x==1)add(a,b,0),add(b,a,0);
        else if(x==2)add(a,b,1);
        else if(x==3)add(b,a,0);
        else if(x==4)add(b,a,1);
        else add(a,b,0);
    }
    for(int i=1;i<=n;i++)add(0,i,1);//虚拟源点建边
    if(spfa())puts("-1");
    else{
        ll res=0;
        for(int i=1;i<=n;i++)res+=dis[i];
        printf("%lld\n",res);
    }
    return 0;
}

网站文章

  • 5个超实用的Visual Studio插件

    5个超实用的Visual Studio插件

    工欲善其事,必先利其器,整理的一些我必装的5款Visual Studio插件,希望你们能get到。01 CodeMaidCodeMaid快速整理代码文件,规范你的代码,提高代码阅读体验。代码自动对齐,...

    2024-02-29 13:30:59
  • 回表查询和聚集索引

    回表查询和聚集索引

    什么是回表查询?这先要从InnoDB的索引实现说起,InnoDB有两大类索引:聚集索引(clustered index) 普通索引(secondary index)InnoDB聚集索引和普通索引有什么...

    2024-02-29 13:30:52
  • Properties类小结

    Properties类的小结

    2024-02-29 13:30:46
  • C++定义一个N*M的矩阵类

    #include&lt;iostream&gt; using namespace std; template&lt;class T&gt; class Matrix{ public: Matrix(int N, int M); //构造函数 Matrix(const Matrix &amp;mat); //拷贝构造函数 ~Matrix(...

    2024-02-29 13:30:39
  • linux centos7 docker Dockerfile 构建springboot镜像并输入日志到宿主机及使用宿主机的application.yml

    linux centos7 docker Dockerfile 构建springboot镜像并输入日志到宿主机及使用宿主机的application.yml

    linux centos7 docker Dockerfile 构建springboot镜像并输入日志到宿主机及使用宿主机的application.yml

    2024-02-29 13:30:10
  • 基于区块链的物流解决方案

    基于区块链的物流解决方案

    科技进步与数字化的发展促成了所谓数字经济的形成,不过对这个术语有许多种解释,根据其中一种解释的说法,数字化被理解为一种在混合现实中运行的经济体。在毛球科技看来,实施这一进程的主要条件包括信息和通信技术...

    2024-02-29 13:30:04
  • mysql索引优化

    mysql索引优化

    mysql索引优化

    2024-02-29 13:29:58
  • mount -t nfs 出现的问题 svc: failed to register lockdv1 RPC service (errno 111).

    mount -t nfs 192.168.1.5:/home/armel /mnt 返回下面的错误: 引用: svc: failed to register lockdv1 RPC service (errno 111). lockd_up: makesock failed, error=-111 mount: mounting 192.168.1.5:/h

    2024-02-29 13:29:30
  • python 的垃圾回收机制?

    python 中的垃圾回收机制是以引用计数为主,分代收集为辅 引用计数,当一个对象的引用数为 0时,python 虚拟机就会回收这个对象的内存。出现循环引入的问题,引入 gc 模块,解决循环引用的问题, gc 模块自动垃圾回收机制,主要作用就是发现并处理不可达的垃圾对 象,采用分代收集的方法,将对象分为三代,一开始,对象在创建的时候,放在一代,如果一次一代的检查中,对象存活...

    2024-02-29 13:29:24
  • 【设计模式】建造者模式 (Builder Pattern)

    【设计模式】建造者模式 (Builder Pattern)

    建造者模式

    2024-02-29 13:29:19