P1477 [NOI2008] 假面舞会题解

water_tomato · 2021-08-19 21:13:10 · 题解

本文同步发表于个人博客：Link。

题目链接。

发现题解区说大多都是直接说再连一条边权为 -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;
}

P1477 [NOI2008] 假面舞会 题解

解析

代码

P1477 [NOI2008] 假面舞会题解