昌平网站制作公司,苏州有实力的软件开发公司,网站空间域名每年都得交吗,上海百度竞价一.缩点的概念 缩点#xff0c;也称为点缩法#xff08;Vertex Contraction#xff09;#xff0c;是图论中的一种操作#xff0c;通常用于缩小图的规模#xff0c;同时保持了图的某些性质。这个操作的目标是将图中的一些节点合并为一个超级节点#xff0c;同时调整相关…一.缩点的概念 缩点也称为点缩法Vertex Contraction是图论中的一种操作通常用于缩小图的规模同时保持了图的某些性质。这个操作的目标是将图中的一些节点合并为一个超级节点同时调整相关边以便保持图的连通性和其他性质。
具体步骤如下 选择一个要缩点的节点选择图中的一个节点将它合并到另一个节点上。 合并节点将选定的节点合并到另一个节点上形成一个新的超级节点。通常情况下选择入度或出度较小的节点进行合并以减小新图的规模。 调整边将与被合并节点相邻的边重新连接到新的超级节点上。注意要避免重复边和自环。 重复步骤1~3继续选择节点进行缩点直到不满足合并条件为止。
缩点操作通常用于算法设计和图分析中有时可以用来简化图的复杂性减少问题的规模。在一些情况下缩点操作可能会破坏某些图的属性因此在使用时需要谨慎考虑。此外缩点操作后的图可能不再是原始问题的精确表示可能会导致问题的近似解。 二.缩短的作用
把一个环缩为一个超级点可以由有环图--DAG从而更好的解决问题。
总之就是我们不想要环直接缩为一个点我们可以更好地解决问题就就可以使用缩点法。 三.模板题
P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 四.思路
1.求点权之和最大我们可以想到什么最小生成树。
2.但这只需要解决一条路径的点权值最大那可以怎么解决拓扑DP。
3.但是...拓扑只能解决DAG这有环啊!!! 我们把环缩成一个超级点然后再建一个新图不就行了吗理论通过实践开始 五.实践
1tarjan缩点
主函数部分
scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,p[i]);}for(int i1;im;i){int u,v;scanf(%d%d,u,v);add(u,v);}for(int i1;in;i){if(!dfn[i]) tarjan(i);}
tarjan:
void tarjan(int u){dfn[u]low[u]num;sta[top]u;ins[u]1;for(int ihead[u];i;iedge[i].next){int vedge[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 j0;while(1){jsta[top--];ins[j]0;h[j]u; //j从此属于u if(ju) break;p[u]p[j]; //点权值合并到第一个点u点上 }}
} 2重新建图 for(int i1;im;i){int uh[edge[i].u],vh[edge[i].v];if(u!v){ //不在一个环 add2(u,v);in[v]; //入度拓扑用 }}
3拓扑排序DP
int topu(){queueint q;for(int i1;in;i){ if(!in[i] ih[i]){q.push(i); //这是这条路径的起点 dp[i]p[i]; //记得赋值 } }//拓扑基础 while(!q.empty()){int kq.front(); q.pop();for(int ihead2[k];i;ied[i].next){int ved[i].v;dp[v]max(dp[v],dp[k]p[v]);in[v]--;if(!in[v]) q.push(v);}}//找最大值不一定n就最大毕竟不止一条路 int ans0;for(int i1;in;i){ansmax(ans,dp[i]);}return ans;
} 六.参考代码完整代码
#includebits/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 ihead[u];i;iedge[i].next){int vedge[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 j0;while(1){jsta[top--];ins[j]0;h[j]u; //j从此属于u if(ju) break;p[u]p[j]; //点权值合并到第一个点u点上 }}
}
int in[maxn],dp[maxn];
int topu(){queueint q;for(int i1;in;i){ if(!in[i] ih[i]){q.push(i); //这是这条路径的起点 dp[i]p[i]; //记得赋值 } }//拓扑基础 while(!q.empty()){int kq.front(); q.pop();for(int ihead2[k];i;ied[i].next){int ved[i].v;dp[v]max(dp[v],dp[k]p[v]);in[v]--;if(!in[v]) q.push(v);}}//找最大值不一定n就最大毕竟不止一条路 int ans0;for(int i1;in;i){ansmax(ans,dp[i]);}return ans;
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,p[i]);}for(int i1;im;i){int u,v;scanf(%d%d,u,v);add(u,v);}for(int i1;in;i){if(!dfn[i]) tarjan(i);}for(int i1;im;i){int uh[edge[i].u],vh[edge[i].v];if(u!v){ //不在一个环 add2(u,v);in[v]; //入度拓扑用 }}couttopu();return 0;
}
