图论缩点的综合应用一

一.缩点的概念

 缩点，也称为点缩法（Vertex Contraction），是图论中的一种操作，通常用于缩小图的规模，同时保持了图的某些性质。这个操作的目标是将图中的一些节点合并为一个超级节点，同时调整相关边，以便保持图的连通性和其他性质。

具体步骤如下：

1. 选择一个要缩点的节点：选择图中的一个节点，将它合并到另一个节点上。

2. 合并节点：将选定的节点合并到另一个节点上，形成一个新的超级节点。通常情况下，选择入度或出度较小的节点进行合并，以减小新图的规模。

3. 调整边：将与被合并节点相邻的边重新连接到新的超级节点上。注意要避免重复边和自环。

4. 重复步骤1~3：继续选择节点进行缩点，直到不满足合并条件为止。

缩点操作通常用于算法设计和图分析中，有时可以用来简化图的复杂性，减少问题的规模。在一些情况下，缩点操作可能会破坏某些图的属性，因此在使用时需要谨慎考虑。此外，缩点操作后的图可能不再是原始问题的精确表示，可能会导致问题的近似解。

二.缩短的作用 

把一个环缩为一个超级点，可以由有环图-->DAG，从而更好的解决问题。

总之就是我们不想要环，直接缩为一个点，我们可以更好地解决问题，就就可以使用缩点法。

三.模板题

P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

四.思路

1.求点权之和最大，我们可以想到什么？最小生成树。

2.但这只需要解决一条路径的点权值最大，那可以怎么解决？拓扑 DP。

3.但是...拓扑只能解决DAG，这有环啊!!! 我们把环缩成一个超级点，然后再建一个新图不就行了吗？理论通过，实践开始！

五.实践

（1）tarjan缩点

主函数部分：

1.  
   scanf("%d%d",&n,&m);
2.  
   for(int i=1;i<=n;i ){
3.  
   scanf("%d",&p[i]);
4.  
   }
5.  
   for(int i=1;i<=m;i ){
6.  
   int u,v;
7.  
   scanf("%d%d",&u,&v);
8.  
   add(u,v);
9.  
   }
10.  
    for(int i=1;i<=n;i ){
11.  
    if(!dfn[i]) tarjan(i);
12.  
    }

tarjan:

1.  
   void tarjan(int u){
2.  
   dfn[u]=low[u]= num;
3.  
   sta[ top]=u;
4.  
   ins[u]=1;
5.  
   for(int i=head[u];i;i=edge[i].next){
6.  
   int v=edge[i].v;
7.  
   if(!dfn[v]){
8.  
   tarjan(v);
9.  
   low[u]=min(low[u],low[v]);
10.  
    }else if(ins[v]){
11.  
    low[u]=min(low[u],dfn[v]);
12.  
    }
13.  
    }
14.  
    if(dfn[u]==low[u]){
15.  
    int j=0;
16.  
    while(1){
17.  
    j=sta[top--];
18.  
    ins[j]=0;
19.  
    h[j]=u; //j从此属于u
20.  
    if(j==u) break;
21.  
    p[u] =p[j]; //点权值合并到第一个点（u点）上
22.  
    }
23.  
    }
24.  
    }

（2）重新建图

1.  
   for(int i=1;i<=m;i ){
2.  
   int u=h[edge[i].u],v=h[edge[i].v];
3.  
   if(u!=v){ //不在一个环
4.  
   add2(u,v);
5.  
   in[v] ; //入度 ，拓扑用
6.  
   }
7.  
   }

（3）拓扑排序 DP

1.  
   int topu(){
2.  
   queue<int> q;
3.  
   for(int i=1;i<=n;i ){
4.  
   if(!in[i] && i==h[i]){
5.  
   q.push(i); //这是这条路径的起点
6.  
   dp[i]=p[i]; //记得赋值
7.  
   }
8.  
    
9.  
   }
10.  
    //拓扑基础
11.  
    while(!q.empty()){
12.  
    int k=q.front(); q.pop();
13.  
    for(int i=head2[k];i;i=ed[i].next){
14.  
    int v=ed[i].v;
15.  
    dp[v]=max(dp[v],dp[k] p[v]);
16.  
    in[v]--;
17.  
    if(!in[v]) q.push(v);
18.  
    }
19.  
    }
20.  
    //找最大值，不一定n就最大，毕竟不止一条路
21.  
    int ans=0;
22.  
    for(int i=1;i<=n;i ){
23.  
    ans=max(ans,dp[i]);
24.  
    }
25.  
    return ans;
26.  
    }

六.参考代码（完整代码）

1.  
   #include<bits/stdc .h>
2.  
   #define maxn 100005
3.  
   using namespace std;
4.  
   int n,m;
5.  
   int p[maxn];
6.  
   struct Edge{
7.  
   int u,v,next;
8.  
   }edge[maxn],ed[maxn];
9.  
   int head[maxn],head2[maxn],cnt,cnt2;
10.  
    void add(int u,int v){
11.  
    edge[ cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
12.  
    }
13.  
    void add2(int u,int v){
14.  
    ed[ cnt2]=(Edge){u,v,head2[u]}; head2[u]=cnt2;
15.  
    }
16.  
    int dfn[maxn],low[maxn],num;
17.  
    int sta[maxn],ins[maxn],top;
18.  
    int lg,h[maxn]; //环的个数，成员属于哪个环
19.  
    void tarjan(int u){
20.  
    dfn[u]=low[u]= num;
21.  
    sta[ top]=u;
22.  
    ins[u]=1;
23.  
    for(int i=head[u];i;i=edge[i].next){
24.  
    int v=edge[i].v;
25.  
    if(!dfn[v]){
26.  
    tarjan(v);
27.  
    low[u]=min(low[u],low[v]);
28.  
    }else if(ins[v]){
29.  
    low[u]=min(low[u],dfn[v]);
30.  
    }
31.  
    }
32.  
    if(dfn[u]==low[u]){
33.  
    int j=0;
34.  
    while(1){
35.  
    j=sta[top--];
36.  
    ins[j]=0;
37.  
    h[j]=u; //j从此属于u
38.  
    if(j==u) break;
39.  
    p[u] =p[j]; //点权值合并到第一个点（u点）上
40.  
    }
41.  
    }
42.  
    }
43.  
    int in[maxn],dp[maxn];
44.  
    int topu(){
45.  
    queue<int> q;
46.  
    for(int i=1;i<=n;i ){
47.  
    if(!in[i] && i==h[i]){
48.  
    q.push(i); //这是这条路径的起点
49.  
    dp[i]=p[i]; //记得赋值
50.  
    }
51.  
     
52.  
    }
53.  
    //拓扑基础
54.  
    while(!q.empty()){
55.  
    int k=q.front(); q.pop();
56.  
    for(int i=head2[k];i;i=ed[i].next){
57.  
    int v=ed[i].v;
58.  
    dp[v]=max(dp[v],dp[k] p[v]);
59.  
    in[v]--;
60.  
    if(!in[v]) q.push(v);
61.  
    }
62.  
    }
63.  
    //找最大值，不一定n就最大，毕竟不止一条路
64.  
    int ans=0;
65.  
    for(int i=1;i<=n;i ){
66.  
    ans=max(ans,dp[i]);
67.  
    }
68.  
    return ans;
69.  
    }
70.  
    int main(){
71.  
    scanf("%d%d",&n,&m);
72.  
    for(int i=1;i<=n;i ){
73.  
    scanf("%d",&p[i]);
74.  
    }
75.  
    for(int i=1;i<=m;i ){
76.  
    int u,v;
77.  
    scanf("%d%d",&u,&v);
78.  
    add(u,v);
79.  
    }
80.  
    for(int i=1;i<=n;i ){
81.  
    if(!dfn[i]) tarjan(i);
82.  
    }
83.  
    for(int i=1;i<=m;i ){
84.  
    int u=h[edge[i].u],v=h[edge[i].v];
85.  
    if(u!=v){ //不在一个环
86.  
    add2(u,v);
87.  
    in[v] ; //入度 ，拓扑用
88.  
    }
89.  
    }
90.  
    cout<<topu();
91.  
    return 0;
92.  
    }
93.  
     

这篇好文章是转载于：编程之路