P6037 Ryoku 的探索题解 » 老官童鞋gogo的博客

题目传送门

题解

题目理解与强调

题目给出的是一个$n$个点$n$条边的无向连通图，$n$个点$n$条边可以看出这是一个基环树，树上每个点都有两种权值，分别表示美观度和长度，我们从一个点出发的时候，要找美观度最大的一条边走，如果那个点已经被走过了，就不走了，换向另一条边，过程类似于DFS。

思路分析

既然是在一棵基环树上遍历每个点，走过这$n$个点需要经过$n-1$条边，用总长度边权减去剩下的那一条没走的边的长度，就是每个点的答案，因为在这个图中有且仅有一个环，那么我们那一条没有走的边一定在环上，如果这一条没走过的边不在环上，至少一个点就不会被遍历到，因为不在环上的点只有一个方向可以到达。

对于判断环，采用拓扑排序，将所有入度为$1$（原图是无向图）的点加入队列，队列为空时，剩下的部分就是环，因为环上的每个点的入度至少为$2$。

为了尽可能减少实际时间复杂度，不去以每个点为起点遍历整张图，而是以环上的点为起点遍历整张图，因为取环上的点为起点遍历部分图，假如环上的一个点$x$，它的周围有两个在环上的点$u$和$v$，如果点$x$到$u$的边上的美观度大于点$x$到$v$上的美观度，那么下一次走的边就是$x \rightarrow u$这一条，另一条$x \rightarrow v$就是第一段中分析的不会经过的边，统计答案的时候减去这条边的长度即可。

那么在整张图上有哪些点会用到我们当前点上算出的答案？我们想象将环上的每一条边都断开，整张图会成为一个森林，规定原先在环上的点为每一棵树上的根节点，每棵树上的所有节点答案都与根节点算出的答案相同。因为每棵树上除了根节点，其他的点都不在环上，而它们走到环上去遍历其他点的路径只有一条，就是经过它们的根节点，所以它们没有走过的边与它们根节点没有走过的边是相同的，答案也是相同的。至此，问题解决。

时间复杂度分析

第一步拓扑排序：$O(n)$

第二步计算答案：$O(n)$

总复杂度：

$$ O(n) $$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 1000001
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct Node
{
    int to,nxt,w,p;
}e[3000001];
int g[3000001],nxt,n,inp[3000001];
bool cir[3000001],vis[3000001];
ll ans[3000001],sum;
queue<int>q;
void add(int x,int y,int w,int p)
{
    e[++nxt].to=y;
    e[nxt].nxt=g[x];
    g[x]=nxt;
    e[nxt].w=w;
    e[nxt].p=p;
}
void find_circle()
{
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        cir[x]=1;
        for(int k=g[x];k;k=e[k].nxt)
        {
            int y=e[k].to;
            inp[y]--;
            if(inp[y]==1)
                q.push(y);
        }
    }
}
void dfs(int x,ll Minw)
{
    // pr(x);
    ll Minp=1e18;
    if(cir[x]==0)
        for(int k=g[x];k;k=e[k].nxt)
        {
            if(Minp>e[k].p&&cir[e[k].to]==0)
            {
                Minp=e[k].p;
                Minw=e[k].w;
            }
        }
    ans[x]=sum-Minw;
    for(int k=g[x];k;k=e[k].nxt)
    {
        int y=e[k].to;
        if(vis[k]==0&&cir[y]!=0)
        {
            vis[k]=1;
            dfs(y,Minw);
        }
    }
}
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),w=read(),p=read();
        add(x,y,w,p);
        add(y,x,w,p);
        inp[y]++;
        inp[x]++;
        sum+=w;
    }
    for(int i=1;i<=n;i++)
    {
        if(inp[i]==1)
            q.push(i);
    }
    find_circle();
    for(int i=1;i<=n;i++)
    {
        if(cir[i]==0)
            dfs(i,0);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

我的代码空间复杂度并不理想，开了$O2$勉强过，若有更优方法请在评论中指出。