P3387缩点


tarjan缩点+记忆化搜索/拓扑+dp

生成新图和老图一定不要搞乱

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,m,num=0,tot=0,t_num=0;
int w[maxn],head[maxn],dfn[maxn],low[maxn],insta[maxn],belong[maxn],dp[maxn];
int num1=0,head1[maxn],sum[maxn],ans=0;
stack<int> s;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*t;
}
struct edge{
    int v,next;
}e[maxn],e1[maxn];
void add(int u,int v)
{
    e[++num].v=v;
    e[num].next=head[u];
    head[u]=num;
}
void add1(int u,int v)
{
    e1[++num1].v=v;
    e1[num1].next=head1[u];
    head1[u]=num1;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++tot;
    s.push(x);
    insta[x]=1;
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(insta[v]) low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        int t;
        t_num++;
        do
        {
            t=s.top();
            s.pop();
            insta[t]=0;
            belong[t]=t_num;
            sum[t_num]+=w[t];
        }while(t!=x);
    }
}
void f(int x)
{
    if(dp[x]) return;
    dp[x]=sum[x];
    int tot=0;
    for(int i=head1[x];i;i=e1[i].next)
    {
        int v=e1[i].v;
        if(!dp[v]) f(v);
        tot=max(tot,dp[v]);
    }
    dp[x]+=tot;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) w[i]=read();
    int x[maxn],y[maxn];
    for(int i=1;i<=m;i++)
    {
        x[i]=read(),y[i]=read();
        add(x[i],y[i]);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i]) tarjan(i);
    for(int i=1;i<=m;i++)
        if(belong[x[i]]!=belong[y[i]])
        add1(belong[x[i]],belong[y[i]]);

    for(int i=1;i<=t_num;i++)
    if(!dp[i])
    {
        f(i);
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ3522最小差值生成树 POJ3522最小差值生成树
最小生成树有一个很重要的性质,生成树不一定是唯一的但每个生成树的每个边权相同,所以不存在a+b=c+d然后都是最小生成树的情况,所以最小值确定最大值也是确定,所以可以枚举最小值多次生成树来判断 #include<iostream>
2019-07-05
下一篇 
P2835刻录光盘 P2835刻录光盘
神tm快读能超时,真是神奇 #include<bits/stdc++.h> using namespace std; const int maxn=20000; int n,num=0,t_num=0,tot=0,ans=0; in
2019-07-05
  目录