[NOI2008]假面舞会

发表于 | 分类于

题目

一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面 具。

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

INPUT

输入文件第一行包含两个整数n, m，用一个空格分隔，n 表示主办方总共准备了多少个面具，m 表示栋栋收集了多少条信息。
接下来m 行，每行为两个用空格分开的整数a, b，表示戴第a 号面具的人看到了第b 号面具。相同的数对a, b 在输入文件中可能出现多次。

OUTPUT

输出文件包含两个数，第一个数为最大可能的面具类数，第二个数为最小可能的面具类数。如果无法将所有的面具分为至少3 类，使得这些信息都满足，则认为栋栋收集的信息有错误，输出两个-1。

SAMPLE

input 1st

6 5
1 2
2 3
3 4
4 1
3 5

output 1st

4 4

input 2nd

3 3
1 2
2 1
2 3

output 2nd

-1 -1

解题报告

当时考试的时候，一看这种带顺序的类似图论的奇怪东西，就想到了拓扑排序
然后……
并不会打拓扑啊QAQ，于是打了个奇（chun）奇（dao）怪（bao）怪（zha）的dfs，好像拿了个特判的-1 -1的分QAQ
正解仍然是dfs
由题目可知，从一个点连出去的点标号一样，几个点指向同一个点，标号也肯定一样。而且，有一句很重要的话：

戴第k 类面具的人能看到戴第1 类面具的人的编号。

那么如果我们找到了环，并将所有环的GCD找出来，我们就找到了最大值。正确性显然= =
如果没有环呢？
显然我们还可以找到链，而链则不会受到上面那个条件的制约，我们就可以很轻松的解决这个问题啦。
然而我们似乎忘记了一个很神奇的东西= =
当我们遇到有各种方向边的环时，显然通过上面的证明，会有第一个点有多个不同标号的情况，这是不可能的，所以，只能看作是不停的由第k个点看第一个点的特殊情况。
如何处理？
很简单，设某个方向边组成的那半个环为ax+k=b的循环，另一个方向边组成的那半个环为cx+k=b的循环。（这里的循环指从第一个点一直走到第k个点再走回第一个点）。显然环是要一样大的，而多出n个环数的点数也应是一样大的（不然起点或终点就会有不止一个标号）。
所以，我们只需建双向边,正边权值1，反边权值-1，最后取个绝对值，就可当正常环看待了（正确性显然= =）

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
struct edge{
    int s,e,n,w;
}a[2000001];
int pre[100001],tot;
inline void insert(int s,int e,int w){
    a[++tot].s=s;
    a[tot].e=e;
    a[tot].w=w;
    a[tot].n=pre[s];
    pre[s]=tot;
}
inline void swp(int &a,int &b){
    a^=b;
    b^=a;
    a^=b;
}
/*inline int gcd(int a,int b){
    //cout<<a<<' '<<b<<endl;
    if(a==0)
        return b;
    if(b==0)
        return a;
    int i,j;
    for(i=0;0==(a&1);i++)
        a>>=1;
    for(j=0;0==(b&1);j++)
        b>>=1;
    if(j<i)
        i=j;
    while(1){
        if(a<b)
            swp(a,b);
        if(0==(a-=b))
            return b<<i;
        while(a&1)
            a>>=1;
    }
}*/
inline int gcd(int a,int b){
    if(a==0)
        return b;
    if(b==0)
        return a;
    return a%b?gcd(b,a%b):b;
}
inline int jdz(int x){
    return x>=0?x:-x;
}
inline int my_min(int a,int b){
    return a<b?a:b;
}
inline int my_max(int a,int b){
    return a>b?a:b;
}
int n,m;
bool vis[100001]={0};
int f[100001]={0};
int mx,mn;
int circle(0),ans(0);
inline void dfs(int u,int cnt){
    if(vis[u])
        return;
    f[u]=cnt;vis[u]=1;
    mx=my_max(mx,cnt);
    mn=my_min(mn,cnt);  
    for(int i=pre[u];i!=-1;i=a[i].n){
        int e(a[i].e);
        if(vis[e]){
            int cir(jdz(cnt-f[e]+a[i].w));
            if(cir){
                if(circle==0)
                    circle=cir;
                else
                    circle=gcd(circle,cir);
            }
        }
        else
            dfs(e,cnt+a[i].w);
    }
}
int main(){
//  freopen("party2008.in","r",stdin);
//  freopen("party2008.out","w",stdout);
    memset(pre,-1,sizeof(pre));
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x(read()),y(read());
        insert(x,y,1);
        insert(y,x,-1);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            mx=-0x7fffffff;
            mn=0x7fffffff;
            dfs(i,0);
            ans+=mx-mn+1;
        }
    if(circle==0){
        if(ans<3){
            printf("-1 -1");
            return 0;
        }
        else{
            printf("%d %d",ans,3);
            return 0;
        }
    }
    else{
        if(circle<3){
            printf("-1 -1");
            return 0;
        }
        else{
            printf("%d ",circle);
            int gg(0);
            for(int i=3;i<=circle;i++){
                if(circle%i==0){
                    gg=i;
                    break;
                }
            }
            if(gg==0)
                printf("%d",circle);
            else
                printf("%d",gg);
        }
    }
}

ps：一直在WA，最后发现是GCD打错了= =
pss：听取蛙声一片啊= =