描述:https://www.luogu.com.cn/problem/P3387

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

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

---

#include
#include
#include
using namespace std;
const int maxn=;
int n,m,p[maxn],dp[maxn];
struct edge{
int u,to,nxt;
}d[maxn*];int head[maxn*],cnt=;
void add(int u,int v){
d[cnt].u=u,d[cnt].to=v,d[cnt].nxt=head[u],head[u]=cnt++;
}
int dfn[maxn],low[maxn],id,stack[maxn],vis[maxn],top,sd[maxn];//为tarjan准备
void tarjan(int now)
{
dfn[now]=low[now]=++id;
stack[++top]=now,vis[now]=;
for(int i=head[now];i;i=d[i].nxt)
{
int w=d[i].to;
if(!dfn[w])
tarjan(w),low[now]=min(low[now],low[w]);
else if(vis[w])
low[now]=min(low[now],low[w]);
}
if(low[now]==dfn[now])
{
int temp;
while(temp=stack[top--])
{
sd[temp]=now;
vis[temp]=;
if(temp==now) break;
p[now]+=p[temp];//集中在now这个超级点上
}
}
}
int indug[maxn];
vectorvec[maxn];
int tuopu()
{
queueq;
for(int i=;i<=n;i++) if(!indug[i]&&sd[i]==i) q.push(i),dp[i]=p[i]; while(!q.empty()) { int now=q.front();q.pop(); for(int i=;i>n>>m;
for(int i=;i<=n;i++) cin>>p[i];//读入点权
for(int i=;i<=m;i++) { int l,r;cin>>l>>r;
add(l,r);
}
for(int i=;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=;i<=m;i++)
{
int x=sd[d[i].u],y=sd[d[i].to];//看看两头是否是连通分量
if(x!=y)//不是就建边
vec[x].push_back(y),indug[y]++;
}
cout<<tuopu();
return ;
}

还有割点的

为什么（“low[v]>=dfn[u]，此时u就是割点”）？？

因为后面的点无法回到u点之前

u就把两个部分分开来了

#include
using namespace std;
const int maxn=;
struct edge{
int nxt,to;
}d[maxn];
int n,m,id,cnt=,ttp;
int head[maxn],dfn[maxn],low[maxn],cut[maxn];
void add(int u,int v){
d[cnt].to=v,d[cnt].nxt=head[u],head[u]=cnt++;
}
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++id;
int child=;
for(int i=head[u];i;i=d[i].nxt)
{
int w=d[i].to;
if(!dfn[w])
{
tarjan(w,fa);
low[u]=min(low[u],low[w]);
if(low[w]>=dfn[u]&&u!=fa)//通过非非节点更新的low[w]
//因为在本连通块能回溯最多到dfn[u]
cut[u]=;
if(u==fa) child++;
}
low[u]=min(low[u],dfn[w]);
}
if(child>=&&u==fa) cut[u]=;
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++) { int l,r; cin>>l>>r;
add(l,r);add(r,l);
}
for(int i=;i<=n;i++)
if(!dfn[i]) tarjan(i,i);
int ans=;
for(int i=;i<=n;i++)
if(cut[i]) ans++;
cout<<ans<<endl;
for(int i=;i<=n;i++)
if(cut[i])
cout<<i<<" ";
return ;
}