【模板】缩点
题目描述
给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式
第一行两个正整数 n,m
第二行 n 个整数，其中第 i 个数 a_i 表示点 i 的点权。
第三至 m+2 行，每行两个整数 u,v，表示一条 u -> v 的有向边。
输出格式
共一行，最大的点权之和。
样例 #1
样例输入 #1
2 2
1 1
1 2
2 1
样例输出 #1
2
#include<bits/stdc++.h>
using namespace std;
#define N 10100
struct node
{
int u,v,ne;
}e[N*10],ed[N*10];//m为n的十倍
int n,m,h[N],hd[N],cnt=0,tim,sum,tp;
int stac[N],dfn[N],vis[N],low[N],sd[N];
int dzhi[N],dsum[N],in[N];
void add1(int u,int v)
{
cnt++;
e[cnt].ne=h[u];
e[cnt].u=u;
e[cnt].v=v;
h[u]=cnt;
}
void add2(int u,int v)
{
cnt++;
ed[cnt].ne=hd[u];
ed[cnt].u=u;
ed[cnt].v=v;
hd[u]=cnt;
}
void tarjan(int x)//缩点
{
low[x]=dfn[x]=++tim;
stac[++tp]=x;
vis[x]=1;
for(int i=h[x];i;i=e[i].ne)
{
int v=e[i].v;
if(!dfn[v])//没有被遍历过
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])//？
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
int y;
while(y=stac[tp--])
{
sd[y]=x;//形成起点为x的缩点
vis[y]=0;
if(x==y)
break;//到联通块头退出
dzhi[x]+=dzhi[y];//缩点后点权sum
}
}
}
int topo()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
if(sd[i]==i && !in[i])//是缩点端点并且//入度为0？？？
{
q.push(i);
dsum[i]=dzhi[i];
}
}
while(!q.empty())
{
int k=q.front();
q.pop();
for(int j=hd[k];j;j=ed[j].ne)
{
int v=ed[j].v;
dsum[v]=max(dsum[v],dsum[k]+dzhi[v]);//求最大点值
in[v]--;
if(in[v]==0)//入度为0,加进去
q.push(v);
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dsum[i]);
return ans;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>dzhi[i];
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
add1(u,v);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
cnt=0;
for(int i=1;i<=m;i++)
{
int x=sd[e[i].u];
int y=sd[e[i].v];
if(x!=y)//不是联通块
{
add2(x,y);
in[y]++;
}
}
cout<<topo()<<"\n";
return 0;
}
```
