P1477 [NOI2008] 假面舞会 题解

发布于 2021-08-19  73 次阅读


题目链接

发现题解区说大多都是直接说再连一条边权为 $-1$ 的边,在这里略微证明一下正确性。​

文章目录

解析

首先发现若图中没有环,最大答案为所有联通块的最长链长度之和,最小答案为 $3$。

若存在环,则最大答案为所有环的 $\gcd$​​。为了在可接受的时间内找到所有环,我们对于每一条边的 $u\rightarrow v$​​,从 $u$​​ 向 $v$​​ 连一条边权为 $1$​​ 的边,从 $v$​​ 向 $u$​​ 连一条边权为 $-1$​​ 的边。然后每一次都从任意一个未被搜索过的点开始搜,并记录每一个点的距离 $dis$​​,若走到一个已走过的点 $i$​​,就取 $d-dis_i$​​ 作为一个新找到的环的长度,这部分代码如下:

inline void dfs(int u,int d){
    if(dis[u]){
        ans=gcd(ans,abs(d-dis[u]));
        return;
    }
    dis[u]=d;vis[u]=1;
    mx=max(mx,dis[u]);mn=min(mn,dis[u]);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;dfs(v,d+e[i].w);
    }
}

接着我们观察下面这张图。

我们发现,当图中出现上图这个情况时,记 $a$​​ 为红色环的长度,$b$​​ 为蓝色部分的长度,$c$​​​ 为中间部分的长度。这时的两个环的长度分别为 $a$​​ 和 $a+b-c$​​,但是我们搜索时搜出来的长度可能是 $a$​​ 和 $c-b$​​​ 或 $a+b-c$ 和 $c-b$,即先搜完 $a$ 这个环,再从 $T$ 点以 $-1$ 的道路通过 $b$ 回到 $S$​​ 点。

也就是说,这个做法想要正确,需要有 $\gcd(a,a+b-c)=\gcd(a,|c-b|)$ 且 $\gcd(a,a+b-c)=\gcd(a+b-c,|c-b|)$​​。

先证明前者:

  • 若 $b \ge c$​,有 $\gcd(a,|c-b|)=\gcd(a,b-c)=\gcd(a,a+b-c)$​,显然正确
  • 若 $b<c$​ ,有 $\gcd(a,|c-b|)=\gcd(a,c-b)=\gcd(a,a+c-b)$​,换言之,我们需要证明 $\gcd(a,a+b)=\gcd(a,a-b),a>b$​。

证明:

记 $x=\gcd(a,a-b)$,则 $x|a$ 且 $x|b$。

设 $a=mx$,$b=nx$,有 $m$ 与 $m-n$ 互质且 $m>n$,故 $\gcd(a,a+b)=\gcd(mx,(m+n)x)$。

若 $m+n$ 与 $m$ 不互质,有 $\gcd(m+n,m)=\gcd(n,m)\ne 1$。

可设 $t=\gcd(m,n)$,有 $m=k_1t,n=k_2t,m-n=(k_1-k_2)t$​​,与 $m$ 与 $m-n$ 互质矛盾。

故 $m+n$​ 与 $m$​ 互质,即 $\gcd(a,a+b)=x=\gcd(a,a-b)$​​。

再证明后者:

  • 若 $c \ge b$,有 $\gcd(a+b-c,|c-b|)=\gcd(a+b-c,c-b)=\gcd(a+b-c,a)$。
  • 若 $c<b$,有 $\gcd(a+b-c,|c-b|)=\gcd(a+b-c,b-c)=\gcd(a+b-c,a+2b-2c)$,将 $a+b-c$ 和 $b-c$ 分别看作 $\gcd(a,a+b)=\gcd(a,a-b)$ 中的 $a$ 和 $b$​,由上得证。

同时我们又发现,除了上图的情况,其他的情况搜到的环的长度都是真是的或是可以化成上图情况的。

因此,建反向的边权为 $-1$ 的边的做法是正确的。求出最大答案后,最小答案显然为最大答案的最小的 $\ge3$ 的因子,求出答案后再判断一下和 $3$​​ 的关系即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
int n,m;
struct node{
    int to,nxt,w;
}e[M];
int cnt,head[N];
inline void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
int dis[N],ans,ans2,mx,mn;
bool vis[N];
inline int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
inline void dfs(int u,int d){
    if(dis[u]){
        ans=gcd(ans,abs(d-dis[u]));
        return;
    }
    dis[u]=d;vis[u]=1;
    mx=max(mx,dis[u]);mn=min(mn,dis[u]);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;dfs(v,d+e[i].w);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v,1);add(v,u,-1);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            mx=-1e9;mn=1e9;
            dfs(i,1);
            ans2+=mx-mn+1;//找最长链
        }
    }
    if(ans){//有环
        if(ans<3) printf("-1 -1\n");
        else for(int i=3;i<=ans;i++){
            if(!(ans%i)){
                printf("%d %d\n",ans,i);
                return 0;
            }
        }
    }
    else{//没环
        if(ans2<3) printf("-1 -1\n");
        else printf("%d 3\n",ans2);
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣