【图论】缩点的综合应用（一）

一.缩点的概念

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

具体步骤如下：

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

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

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

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

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

---

二.缩短的作用 

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

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

---

三.模板题

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

---

四.思路

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

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

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

---

五.实践

（1）tarjan缩点

主函数部分：

scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}

tarjan:

void tarjan(int u){dfn[u]=low[u]=++num;sta[++top]=u;ins[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int j=0;while(1){j=sta[top--];ins[j]=0;h[j]=u; //j从此属于u if(j==u) break;p[u]+=p[j]; //点权值合并到第一个点（u点）上 }}
}

（2）重新建图

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

（3）拓扑排序+DP

int topu(){queue<int> q;for(int i=1;i<=n;i++){ if(!in[i] && i==h[i]){q.push(i); //这是这条路径的起点 dp[i]=p[i];  //记得赋值 } }//拓扑基础 while(!q.empty()){int k=q.front(); q.pop();for(int i=head2[k];i;i=ed[i].next){int v=ed[i].v;dp[v]=max(dp[v],dp[k]+p[v]);in[v]--;if(!in[v]) q.push(v);}}//找最大值，不一定n就最大，毕竟不止一条路 int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i]);}return ans;
}

---

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

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
int p[maxn];
struct Edge{int u,v,next;
}edge[maxn],ed[maxn];
int head[maxn],head2[maxn],cnt,cnt2;
void add(int u,int v){edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
void add2(int u,int v){ed[++cnt2]=(Edge){u,v,head2[u]}; head2[u]=cnt2;
}
int dfn[maxn],low[maxn],num;
int sta[maxn],ins[maxn],top;
int lg,h[maxn]; //环的个数，成员属于哪个环 
void tarjan(int u){dfn[u]=low[u]=++num;sta[++top]=u;ins[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int j=0;while(1){j=sta[top--];ins[j]=0;h[j]=u; //j从此属于u if(j==u) break;p[u]+=p[j]; //点权值合并到第一个点（u点）上 }}
}
int in[maxn],dp[maxn];
int topu(){queue<int> q;for(int i=1;i<=n;i++){ if(!in[i] && i==h[i]){q.push(i); //这是这条路径的起点 dp[i]=p[i];  //记得赋值 } }//拓扑基础 while(!q.empty()){int k=q.front(); q.pop();for(int i=head2[k];i;i=ed[i].next){int v=ed[i].v;dp[v]=max(dp[v],dp[k]+p[v]);in[v]--;if(!in[v]) q.push(v);}}//找最大值，不一定n就最大，毕竟不止一条路 int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i]);}return ans;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=m;i++){int u=h[edge[i].u],v=h[edge[i].v];if(u!=v){ //不在一个环 add2(u,v);in[v]++; //入度++，拓扑用 }}cout<<topu();return 0;
}