园公逛

图论 强联通分量

题面

给定一个有$n$个顶点$m$条边的带权无向图。现有$q$次询问，每次询问$u,v$之间的一条环路径（无重边），要求边权最大值最小，输出这个最大值。

• $10pts$ $n\leq10,m,q\leq15$
• $30pts$ $n\leq1000,m,q\leq1500$
• $50pts$ $n\leq5000,m,q\leq8000$
• $100pts$ $n\leq10^5,m,q\leq5*10^5$

解析

$10pts$算法

暴搜。记得$u->v$和$v->u$的$dfs$过程要连起来，后者从前者引出。
而不是

dfs(u,v,lim);
if(!flag) return;
dfs(v,u,lim);

。。。

边双联通分量vs点双联通分量

边双无割边（转一圈走两次的边）。
点双无割点（转一圈走两次的点）。（一个环）
所以这道题应用边双$tarjan$，与点双唯一的不同是没有$vis$判定过程。

il int tarjan(re int u,re ll lim,re int lst)
{
  dfn[u]=low[u]=++tim;sta[++top]=u;re int v;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      v=e[i].to;
      if(e[i].w>lim||lst==i) continue;
      if(!dfn[v]) tarjan(v,lim,i^1),low[u]=min(low[u],low[v]);
      else low[u]=min(low[u],dfn[v]);
    }
  if(low[u]==dfn[u])
    do
      {
    v=sta[top--];
    f[v]=u;
      }
    while(u^v);
}

$30pts$算法

最大值、最小值，容易想到二分。
于是二分这个值$w$，每次排除掉边权比$w$更大的边，$tarjan$找边强联通分量。
什么，你说这是无向图?
$tarjan$时不走上次走的边的反边就可以啦。
复杂度$O(qnlogn)$

il int check(re int u,re int tar,re ll lim)
{
  top=tim=0;fp(i,1,n) dfn[i]=low[i]=0,f[i]=i;
  fp(i,1,n) if(!dfn[i]) tarjan(i,lim,-1);
  return find(u)==find(tar);
}
int main()
{
  n=gi();m=gi();q=gi();
  memset(h,-1,sizeof(h));
  fp(i,1,n) num[i]=gi();
  fp(i,1,m)
    {
      re int u=gi(),v=gi();ll w=num[u]-num[v];if(w<0) w=-w;
      add(u,v,w);add(v,u,w);if(mx<w) mx=w;if(mn>w) mn=w;
    }
  while(q--)
    {
      re int u=gi(),v=gi();
      re ll l=mn,r=mx,ans=-1;
      while(l<=r)
    {
      re ll mid=l+r>>1;
      if(check(u,v,mid))r=mid-1,ans=mid;
      else l=mid+1;
    }
      ans==-1?puts("No way!"):printf("%lld\n",ans);
    }
  return 0;
}

$50pts$算法

根据题意，把边按从小到大的顺序加入结果显然是最优的。
什么时候会形成环？往最小生成树上加边就会形成环。
于是我们先构建一颗最小生成树。
然后从小到大加上非树边。
每加入一条非树边$(x,y)$，就可以把$x,y$路径间所有的点(环)缩成一个环。它们互相之间都有第二条联通路径相互到达，可视为一体。该操作用新并查集维护。
具体是将这些点的$fa$改变为$x,y$的$lca$（最上面那个点）。
如果加上一条非树边边后，发现$u,v$在同一并查集，就说明他们有了除最小生成树上路径以外的第二条联通路径，满足题意。这条非树边长度就是答案。
复杂度$O(qn)$（并查集被看作常数复杂度）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,q,h[N],cnt,f[N],d[N],ff[N],vis[N];
ll num[N];
struct Edge
{
  int to,nxt;ll w;
}e[N<<1];
struct dat
{
  int u,v,vis;ll w;
  bool operator < (const dat &o) const {return w<o.w;}
}a[N];
il void add(re int u,re int v,re ll w){e[++cnt].to=v;e[cnt].nxt=h[u];e[cnt].w=w;h[u]=cnt;}
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
il void dfs(re int u)
{
  vis[u]=1;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(vis[v]) continue;
      d[v]=d[u]+1;ff[v]=u;
      dfs(v);
    }
}
int main()
{
  freopen("krap.in","r",stdin);
  freopen("krap.out","w",stdout);
  n=gi();m=gi();q=gi();
  memset(h,-1,sizeof(h));
  fp(i,1,n) num[i]=gi(),f[i]=i;
  fp(i,1,m)
    {
      re int u=gi(),v=gi();ll w=num[u]-num[v];if(w<0) w=-w;
      a[i].u=u,a[i].v=v,a[i].w=w;
    }
  sort(a+1,a+1+m);
  fp(i,1,m)
    {
      re int u=a[i].u,v=a[i].v,w=a[i].w,fu=find(u),fv=find(v);
      if(fu^fv)
    {
      a[i].vis=1;
      f[fv]=fu;
      add(u,v,w);add(v,u,w);
    }
    }
  fp(i,1,n) if(!vis[i]) dfs(i);
  while(q--)
  {
    re int uu=gi(),vv=gi();
    re ll ans=-1;
    fp(i,1,n) f[i]=i;
    fp(i,1,m)
      if(!a[i].vis)
      {
    re int u=a[i].u,v=a[i].v,fu=find(u),fv=find(v),pu=fu,pv=fv;
    if(fu^fv)
      {
        while(fu^fv)
          {
        if(d[fu]<d[fv]) swap(fu,fv);
        fu=ff[fu];
          }
        re int lca=fu;
        for(;pu^lca;pu=find(ff[pu])) f[pu]=lca;
        for(;pv^lca;pv=find(ff[pv])) f[pv]=lca;
        if(find(uu)==find(vv)) {ans=a[i].w;break;}
      }
      }
    ans==-1?puts("No way!"):printf("%lld\n",ans);
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}