隐藏
「NOI2008」假面舞会 - 图的遍历+最大公约数 | Bill Yang's Blog
0%

「NOI2008」假面舞会 - 图的遍历+最大公约数

题目大意

    一年一度的假面舞会又开始了,栋栋也兴致勃勃的参加了今年的舞会。
    今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号,主办方会把此编号告诉拿该面具的人。
    为了使舞会更有神秘感,主办方把面具分为$k(k\ge3)$类,并使用特殊的技术将每个面具的编号标在了面具上,只有戴第$i$类面具的人才能看到戴第$i+1$类面具的人的编号,戴第$k$类面具的人能看到戴第$1$类面具的人的编号。
    参加舞会的人并不知道有多少类面具,但是栋栋对此却特别好奇,他想自己算出有多少类面具,于是他开始在人群中收集信息。
    栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第$2$号面具的人看到了第$5$号面具的编号。栋栋自己也会看到一些编号,他也会根据自己的面具编号把信息补充进去。
    由于并不是每个人都能记住自己所看到的全部编号,因此,栋栋收集的信息不能保证其完整性。现在请你计算,按照栋栋目前得到的信息,至多和至少有多少类面具。
    由于主办方已经声明了$k\ge3$,所以你必须将这条信息也考虑进去。


题目分析

本题很特别,需要寻找一定的规律,再使用图论知识解决。

我们发现如果图中有环,那么答案必定由环限制,因为树的最小值显然是$1$。

因此,首先考虑题目不存在环的情况,即一个森林。
森林的最小值显然是$\max(1,3)=3$,最大值为每棵树最长链相加。

考虑,若图中存在环,那么对于一个环,所有环长的约数均可成为答案。
但是一个这样的“环”也可以对答案做出贡献:

其贡献是$\left|a-b\right|$的所有约数,其中$a,b$是该“环”上的两条有向链。
因此我们不妨将原图每一条边对应一条$-1$的反边,找出所有环取$\gcd$即为最大的答案。
然而,找出所有环是没有多项式算法的。
注意到我们只需要求出环的$\gcd$,根据$\gcd$的性质,我们只需要求出Dfs/Bfs树上的返祖边构成的环即可。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005;

struct Edge {
int from,to,dist;
};

int n,m,Dist[maxn],Gcd=0,sum=0;
bool vst[maxn];
vector<Edge>edges[maxn];

void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {x,y,v});
}

int Bfs(int s) {
Dist[s]=0;
int Max=0,Min=0;
queue<int>Q;
Q.push(s);
while(!Q.empty()) {
int Now=Q.front();
Max=max(Max,Dist[Now]);
Min=min(Min,Dist[Now]);
Q.pop();
for(Edge& e:edges[Now]) {
int Next=e.to;
if(vst[Next]) { //环
Gcd=__gcd(Gcd,abs(Dist[Now]+e.dist-Dist[Next]));
continue;
}
vst[Next]=1;
Dist[Next]=Dist[Now]+e.dist;
Q.push(Next);
}
}
return Max-Min+1;
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y,1);
AddEdge(y,x,-1);
}
for(int i=1; i<=n; i++)
if(!vst[i])sum+=Bfs(i);
if(Gcd) {
if(Gcd<3)puts("-1 -1");
else if(Gcd>=1) {
for(int i=3; i<=Gcd; i++)
if(Gcd%i==0) {
printf("%d %d\n",Gcd,i);
break;
}
}
} else if(sum<3)puts("-1 -1");
else printf("%d 3",sum);
return 0;
}
姥爷们赏瓶冰阔落吧~