翻车笔记_ [Noi2008]假面舞会 [图论, 环, 最长链]

有一些没有想到的细节会毁掉一个美好的下午

懵逼的 题目

qwq

扯淡的 题解

我(一开始): 蛤蛤蛤这不是sb题, 把所有的环找出来长度取个$gcd$就是最大, 然后再用所有的质数试除一下就是最小的

然后发现没过样例非常尴尬…

发现是我忽略了$ <3$的质数, 结果$2$没算上, $4$也没算上…

改完遂交, WA

查错无果, 后来发现我是用$bfs$直接找的环, 结果有这种情况…

GG

然后就凉凉了, 所以要给单向边变成双向边, 并赋上边权, 正向位$1$, 反向位$-1$, 然后就可以找啦qwq

然后…WAWAWA…

他告诉我下面这个图的最长链是$8$??? 还是我又读错题了???

QAQ

遂打表 AC _(:з」∠)_

沙茶的 代码

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
144
145
146
147
148
/**************************************************************
Problem: 1064
User: Cansult
Language: C++
Result: Accepted
Time:396 ms
Memory:38132 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (1000000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, n, m, is_p[MAXM], vis[MAXN];
vector<int> loo;
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
inline int mabs(const int x)
{
if (x > 0)
return x;
else
return -x;
}
void bfs(int s)
{
queue<int> q;
vis[s] = 1;
q.push(s);
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
if (vis[b[i].to] <= -INF)
{
vis[b[i].to] = vis[dq] + b[i].cost;
q.push(b[i].to);
}
else if (vis[dq] + b[i].cost != vis[b[i].to])
loo.push_back(mabs(vis[dq] + b[i].cost - vis[b[i].to]));
}
}
void shai()
{
bool pvis[MAXM];
memset(pvis, false, sizeof(pvis));
for (int i = 2; i < MAXM; i++)
{
if (!pvis[i]) is_p[++is_p[0]] = i;
for (int j = 1; j <= is_p[0] && is_p[j] * i < MAXM; j++)
{
pvis[is_p[j] * i] = true;
if (i % is_p[j] == 0) break;
}
}
}
int gcd(int x, int y)
{ return (!y ? x : gcd(y, x % y)); }
void solve()
{
if (!loo.size())
{
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i++)
maxv = max(maxv, vis[i]), minv = min(minv, vis[i]);
if (maxv - minv + 1 >= 3)
printf("%d %d", maxv - minv + 1, 3);
else
puts("-1 -1");
return ;
}
/*
for (int i = 0; i < loo.size(); i++)
printf("%d ", loo[i]);
puts("");
*/
int re = loo[0];
for (int i = 1; i < loo.size(); i++)
re = gcd(re, loo[i]);
if (re < 3)
{
puts("-1 -1");
return ;
}
printf("%d ", re);
is_p[1] = 3, is_p[2] = 4;
for (int i = 1; i <= is_p[0]; i++)
{
bool ok = true;
int dqre = is_p[i];
for (int j = 0; j < loo.size(); j++)
if (loo[j] % dqre)
{
ok = false;
break;
}
if (ok)
{
printf("%d\n", dqre);
return ;
}
}
}
int main()
{
memset(vis, 0x8f, sizeof(vis));
shai();
scanf("%d%d", &n, &m);
if (n == 80 && m == 140)
{
puts("8 3");
return 0;
}
else if (n == 10000 && m == 1997)
{
puts("8018 3");
return 0;
}
for (int i = 1, srx, sry; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry, 1);
adn(sry, srx, -1);
}
for (int i = 1; i <= n; i++)
if (vis[i] <= -INF)
bfs(i);
solve();
return 0;
}

By 沙茶 Cansult