BZOJ1064 - [NOI2008]假面舞会

2017/02/17

题目

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

题解可以看:
Proverbs
PoPoQQQ

关键在于分析出图的拓扑,然后就很容易写了。

代码

 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define out(u, it) for(It it=G[u];it;it=it->n)
using namespace std;
const int MAX_M = 1000000 + 1000;
const int PSIZ = (MAX_M << 1);

struct tgno {
    int v, w;
    tgno* n;
} POOL[PSIZ]; int ppos;
tgno* G[PSIZ];
typedef tgno* It;
int N, M;
int ansmax, ansmin;

void addEdge(int u, int v, int w) {
    POOL[ppos].v = v; POOL[ppos].w = w;
    POOL[ppos].n = G[u];
    G[u] = &POOL[ppos++];
    if(ppos == PSIZ) while(true);
}

int gcd(int a, int b) {
    if(!b) return a;
    else return gcd(b, a % b);
}

int vis[MAX_M], t[MAX_M];
void dfs1(int cur) {
    vis[cur] = 1;
    out(cur, i) {
        if(!vis[i->v]) {
            t[i->v] = t[cur] + i->w; dfs1(i->v);
        } else {
            ansmax = gcd(ansmax, abs(t[cur] + i->w - t[i->v]));
        }
    }
}

int lmax, lmin;
void dfs2(int cur) {
    vis[cur] = 1;
    lmax = max(lmax, t[cur]);
    lmin = min(lmin, t[cur]);
    out(cur, i) {
        if(!vis[i->v]) {
            t[i->v] = t[cur] + i->w;
            dfs2(i->v);
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    
    int u, v;
    for(int i=0;i<M;i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v, 1);
        addEdge(v, u,-1);
    }
    
    for(int i=1;i<=N;i++)
        if(!vis[i]) dfs1(i);
    
    if(ansmax)
        for(ansmin=3;ansmin<ansmax&&ansmax%ansmin;ansmin++);
    else {
        memset(vis, 0, sizeof(vis));
        memset(t, 0, sizeof(t));
        
        for(int i=1;i<=N;i++)
            if(!vis[i]) {
                lmax = lmin = 0;
                dfs2(i);
                ansmax += lmax - lmin + 1;
            }
        ansmin = 3;
    }
    if(ansmax < 3)
        ansmax = ansmin = -1;
    printf("%d %d", ansmax, ansmin);
    
    #ifdef LCYTEST
    getchar(); getchar(); getchar();
    #endif
}