2.17学习总结

2024-02-18 08:20
文章标签 学习 总结 2.17

本文主要是介绍2.17学习总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

tarjan

【模板】缩点https://www.luogu.com.cn/problem/P3387

题目描述

给定一个 �n 个点 �m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

输入格式

第一行两个正整数 �,�n,m

第二行 �n 个整数,其中第 �i 个数 ��ai​ 表示点 �i 的点权。

第三至 �+2m+2 行,每行两个整数 �,�u,v,表示一条 �→�u→v 的有向边。

输出格式

共一行,最大的点权之和。

输入输出样例

输入 #1复制

2 2
1 1
1 2
2 1

输出 #1复制

2

说明/提示

对于 100%100% 的数据,1≤�≤1041≤n≤104,1≤�≤1051≤m≤105,0≤��≤1030≤ai​≤103。

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=1e5+5;struct edge{int from;int to;int next;
}e[N],e1[N];int instack[N];
int s,tot,dfn[N],low[N],head[N],sd[N],dis[N],w[N],m,n,in[N],h[N],sum;
stack<int>st;void add(int u,int v){e[++tot].from=u;e[tot].to=v;e[tot].next=head[u];head[u]=tot;
}void tarjan(int u){dfn[u]=low[u]=++s;st.push(u);instack[u]=1;for (int i=head[u];i;i=e[i].next){int v=e[i].to;if (!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if (instack[v]){low[u]=min(low[u],dfn[v]);}}if (dfn[u]==low[u]){while (!st.empty()){int p=st.top();st.pop();instack[p]=0;sd[p]=u;if (u==p) break;w[u]+=w[p];}}
} int topo(){queue<int>q;for (int i=1;i<=n;++i){if (!in[i] && sd[i]==i){q.push(i);dis[i]=w[i];}}while (!q.empty()){int u=q.front(); q.pop();for (int i=h[u];i;i=e1[i].next){int v=e1[i].to;dis[v]=max(dis[v],dis[u]+w[v]);in[v]--;if (in[v]==0) q.push(v);}}int ans=0;for (int i=1;i<=n;++i){ans=max(ans,dis[i]);}return ans;
}signed main(){cin>>n>>m;for (int i=1;i<=n;++i) cin>>w[i];for (int i=1;i<=m;++i){int u,v;cin>>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 x=sd[e[i].from],y=sd[e[i].to];if (x!=y){e1[++sum].from=x;e1[sum].to=y;e1[sum].next=h[x];h[x]=sum;in[y]++;}}cout<<topo();
}

模板】割点(割顶)https://www.luogu.com.cn/problem/P3388#submit

题目背景

割点

题目描述

给出一个 �n 个点,�m 条边的无向图,求图的割点。

输入格式

第一行输入两个正整数 �,�n,m。

下面 �m 行每行输入两个正整数 �,�x,y 表示 �x 到 �y 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点,用空格隔开。

输入输出样例

输入 #1复制

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

输出 #1复制

1
5

说明/提示

对于全部数据,1≤�≤2×1041≤n≤2×104,1≤�≤1×1051≤m≤1×105。

点的编号均大于 00 小于等于 �n。

tarjan图不一定联通。

#include <bits/stdc++.h>
using namespace std;const int N=2e5+5,M=1e6;struct edge{int from;int to;int next;
}e[M];int s,dfn[N],low[N],head[N],n,m,tot,cut[N];void add(int u,int v){e[++tot].from=u;e[tot].to=v;e[tot].next=head[u];head[u]=tot;
}
void tarjan(int u,int fa){dfn[u]=low[u]=++s;int child=0;for (int i=head[u];i;i=e[i].next){int v=e[i].to;if (!dfn[v]){tarjan(v,fa);low[u]=min(low[u],low[v]);if (dfn[u]<=low[v] && u!=fa){cut[u]=1;}if (u==fa){child++;}}low[u]=min(low[u],dfn[v]);}if (u==fa && child>=2){cut[u]=1;}
}
int main(){cin>>n>>m;for (int i=0;i<m;++i){int u,v;cin>>u>>v;add(u,v);add(v,u);}for (int i=1;i<=n;++i){if (!dfn[i]) tarjan(i,i);}int ans=0;for (int i=1;i<=n;++i){if (cut[i]) ans++;}cout<<ans<<endl;for (int i=1;i<=n;++i){if (cut[i])cout<<i<<" ";}
}

这篇关于2.17学习总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720588

相关文章

Nginx Location映射规则总结归纳与最佳实践

《NginxLocation映射规则总结归纳与最佳实践》Nginx的location指令是配置请求路由的核心机制,其匹配规则直接影响请求的处理流程,下面给大家介绍NginxLocation映射规则... 目录一、Location匹配规则与优先级1. 匹配模式2. 优先级顺序3. 匹配示例二、Proxy_pa

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

Linux区分SSD和机械硬盘的方法总结

《Linux区分SSD和机械硬盘的方法总结》在Linux系统管理中,了解存储设备的类型和特性是至关重要的,不同的存储介质(如固态硬盘SSD和机械硬盘HDD)在性能、可靠性和适用场景上有着显著差异,本文... 目录一、lsblk 命令简介基本用法二、识别磁盘类型的关键参数:ROTA查询 ROTA 参数ROTA

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi