NOI2008

NOI2008

假面舞会

首先最大面具数就是这个有向图上所有环长的\(\gcd\),最小个数就是最大面具数的\(\ge 3\)的最小因子。特别的如果没有环的话最大面具数就是所有子图中最长链的和,最小个数就是三。(如果最大面具数\(<3\)就是无解)

然后我们会发现一种鬼畜的情况,如图:

虽然它满足最长链\(\ge 3\),但实际上它是无解的。实际上我们把正边的边权看成\(1\),反边的边权看成\(-1\),然后定义环的权值为环上的边权和的绝对值然后求一遍\(\gcd\)就完美的解决了这个问题。

代码:

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
/*
* 1064.cpp
* This file is part of 1064
*
* Copyright (C) 2019 - ViXbob
*
* 1064 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 1064 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 1064. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, m, dfn[maxn], instack[maxn], mn, mx, deg[maxn], ans, tmp;
vector<pair<int, int> > G[maxn];
map<pair<int, int>, bool> mp;

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

inline void dfs(int x, int d) {
mx = max(d, mx); mn = min(d, mn);
instack[x] = d; dfn[x] = ++dfn[0];
for(auto [v, w] : G[x]) {
if(dfn[v]) {
ans = __gcd(ans, abs(d + w - instack[v]));
// cerr << x << " -> " << v << ", w = " << w << endl;
// cerr << d + w - instack[v] << endl;
} else dfs(v, d + w);
}
}

int main() {
// freopen("2.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read();
rep(i, 1, m) {
int x = read(), y = read();
if(mp.count(mp(y, x))) { cout << -1 << " " << -1 << endl; return 0; }
if(mp.count(mp(x, y))) continue;
mp[mp(x, y)] = true;
G[x].pb(mp(y, 1)); G[y].pb(mp(x, -1));
}
rep(i, 1, n) if(!dfn[i]) {
mx = -inf; mn = inf;
dfs(i, 0);
tmp += mx - mn + 1;
}
rep(i, 3, ans) if(ans % i == 0) { cout << ans << " " << i << endl; return 0; }
if(tmp >= 3 && ans == 0) { cout << tmp << " " << 3 << endl; return 0; }
cout << -1 << " " << -1 << endl;
return 0;
}

道路设计