P3916 图的遍历

chichichichi · 2020-09-26 22:21:46 · 个人记录

躺在收藏列表里很久很久很久的一道（水）题…。

然而这次大概也不是用正解做出来的,我甚至想不明白为什么这样做能过

思路

1 > 建反图

2 > 套最短路模板 （最短路真好用）

F [ i ] 存储 i 节点 能到达的最大编号

初始化：

    f[i]=i;

松弛操作：

    int y=to[i];
    if(f[y]<max(to[i],f[x]))
            f[y]=max(to[i],f[x]);

从编号为n的节点开始，从大到小跑最短路，这样可以更快得到答案，不然会TLE

每次最短路不重置F数组的值

3 > 输出F数组

疑问

在写这篇博客的时候感觉代码有些地方可以更简洁，但是在修改后尝试提交发现并不能进行修改

先贴上代码

    for(int i=lin[x];i;i=ne[i])
        {
            int y=to[i];
            if(f[y]<max(to[i],f[x]))
            {
                flag++;
                f[y]=max(to[i],f[x]);
                q.push(make_pair(-f[y],y));
            }
        }

• F[ y ]初始化为 y,松弛操作是将F[ y ]与max( y , F[ x ] )进行比较

我认为这里可以改为

    if(f[y]<f[x])

但是我修改之后再次提交测评了两次，发现分别TLE了一个点和两个点。

显然是此处修改导致入队次数增加，但我不明白为什么会出现这样的情况，求dalao解答

• upload:将我修改后的全部松弛操作贴了上来，因为@wqy_03 dalao只修改了下面的伪AC代码中的if判断，进行提交测评，AC了此题，而我其实还修改了if中的赋值操作（代码如下），结果TLE

  if(f[y]<f[x])
  {
      flag++;
      f[y]=f[x];
      q.push(make_pair(-f[y],y));
  }

  第一次AC记录（使用max()）

80tips TLE测评记录（使用max()）

80tips TLE测评记录（无max()）

AC dalao修改后测评记录（if无max() 赋值有max()）

（越来越玄学了？）

最后

是伪AC代码

• upload:删去了代码中无用变量以改善阅读体验

• upload:@wqy_03 dalao发现此AC代码再次测评TLE，我进行提交发现确实如此

  #include<cstdio>
  #include<queue>
  #include<cstring>
  #include<iostream>
  using namespace std;
  const int maxn=1e5+10;
  int n,m,tot;
  int lin[maxn],to[maxn],ne[maxn];
  void add(int u,int v)
  {
  to[++tot]=v;
  ne[tot]=lin[u];
  lin[u]=tot; 
  }
  int f[maxn],vis[maxn];
  priority_queue<pair<int,int> >q;
  void dij(int s)
  {
  memset(vis,0,sizeof(vis));
  q.push(make_pair(-s,s));
  while(!q.empty())
  {
      int x=q.top().second;
      q.pop();
      if(vis[x])
      continue;
      vis[x]=1;
      for(int i=lin[x];i;i=ne[i])
      {
          int y=to[i];
          if(f[y]<max(to[i],f[x]))
          {
              f[y]=max(to[i],f[x]);
              q.push(make_pair(-f[y],y));
          }
      }
  }
  }
  int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
      int a,b;
      scanf("%d%d",&a,&b);
      add(b,a);
  }
  for(int i=1;i<=n;i++)
  f[i]=i;
  for(int i=n;i>=1;i--)
      dij(i);
  
  for(int i=1;i<=n;i++)
  printf("%d ",f[i]);
  return 0;
  }

Solved

感谢@rcxkk dalao

三份代码都能AC（详见评论），测评姬的心情波动比较大（xxx）

所以下次写正解吧