题解 P5145 【漂浮的鸭子】

06ray · 2018-12-23 22:13:24 · 题解

裸的最大环问题

由于图是单向的，所以我们可以用tarjan来求强连通分量，把每个环中每个边的时间累加起来，最后打个擂台统计最大的就行了。

代码:

#include <iostream> 
#include <vector>
#include <stack>
using namespace std;
const int MAXN=501000;
stack<int> s;
int n,m,x[MAXN],y[MAXN],dfn[MAXN],low[MAXN],color[MAXN],vis[MAXN],used[MAXN],in[MAXN],f[MAXN],a[MAXN],b[MAXN];
int colornum; 
vector<int> G[MAXN];
int cnt;
void tarjan(int u)//tarjan模板，不解释
{
    cnt++;
    dfn[u]=low[u]=cnt;
    used[u]=true;
    s.push(u);
    vis[u]=true;
    for(int i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        {
            if(vis[v])
            {
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(dfn[u]==low[u])
    {
        colornum++;
        while(s.top()!=u)
        {
            int t=s.top();
            s.pop();
            color[t]=colornum;
            vis[t]=false;
        }
        s.pop();
        color[u]=colornum;
        vis[u]=false;
    }
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>x[i]>>y[i];
        G[i].push_back(x[i]);//建图
    }
    for(int i=1; i<=n; i++)
    if(!used[i]) tarjan(i);
    for(int i=1; i<=n; i++)
    {
        b[color[i]]+=y[i];//累加
    }
    int ans=0;
    for(int i=1; i<=colornum; i++)
    {
        if(b[i]!=1)ans=max(ans,b[i]);//打擂台，求最大值
    }
    cout<<ans;
    return 0;
}

双倍经验