求最小环的几种姿势

一连碰到了几道关于环的题。。结果一道都没过。。

无向图

Floyd

memcpy(dis,g,sizeof(dis));
for(int k=1;k<=n;k++){
  for(int i=1;i<k-1;i++)
    for(int j=i+1;j<k;j++)
      ans=min(ans,dis[i][j]+g[i][k]+g[k][j]);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

最小生成树

此法有误，因为最小环上的边可能不止一条没有在最小生成树上，不能通过加边获得最小环。

有向图

Floyd

memcpy(dis,g,sizeof(g));
for(int k=1;k<=n;k++)
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
    ans=min(ans,g[i][j]+dis[j][i]);

DFS

适用于简单环。

void dfs(int u,int cdep){
  tag[u]=cnt,dep[u]=cdep;
  for(int i=now[u];i;i=nxt[i]){
    int v=to[i];
    if(dep[v]){
      if(tag[v]==cnt)ans=min(ans,dep[u]-dep[v]+1);
      continue;
    }
    dfs(v,cdep+1);
  }
}

Dijkstra

首先将源点的$dist$dist设为$0$0，源点出堆后把$dist$dist改为$\infty$∞，下一次源点的$dist$dist更新的值就是经过源点的最小环的长度。

Tarjan

当每个点的出度为$1$1 时，最小环的长度就是所有强连通分量（单个点除外）大小的最小值。

并查集

适用于简单环。

int find(int x){
  if(fa[x]==x)return x;
  int anc=find(fa[x]);
  d[x]+=d[fa[x]];
  return fa[x]=anc;
}
void merge(int x,int y){
  int fx=find(x),fy=find(y);
  if(fx!=fy)fa[fx]=fy,d[x]=d[y]+1;
  else ans=min(ans,d[x]+d[y]+1);
}

拓扑排序

先进行一次拓扑排序，把不在环上的点删掉，再从未讨论的点进行dfs，统计最小环的大小。适用于简单环。

int dfs(int u){
  if(vis[u])return 0;
  vis[u]=1;
  for(int i=head[u];i!=-1;i=ed[i].next){
    int v=ed[i].to;
    return 1+dfs(v);
  }
}

toposort();
for(int i=1;i<=n;i++)
  if(ind[i]&&!vis[i])ans=min(ans,dfs(i));