Processing math: 100%
CF1240F Football

神仙构造题。写一下 pb 讲的做法。

考虑极差不超过 2 这个限制。可以把每条边 u,v ,令 u<v ,则变成 u,v+n 的一条边,也就是拆成一个二分图。

考虑在这个图上染色,然后再把 u,u+n 合并起来。如果在这个得到的二分图上可以染色使得每个点极差不超过 1 ,那么合并后一定可以让每个点极差不超过 2

下面将说明这样的合法的染色方案一定存在。假设一个点 u 的度数是 ak+b ,那么我们可以把一个点拆成 a+1 个点,然后前 a 个点分别得到原二分图上 u 的任意 k 个出边,最后一个得到 b 个出边。然后我们就需要染色后使得每个点的的所有出边颜色不同。

考虑一条边一条边进行染色。假设当前边的两端是 u,v 。现在我们任意找到 u,v 的一对还没有用过的颜色 cu,cv 。如果有 cu=cv ,显然可以直接给这条边染色。否则,我们把这条边置为 cu ,然后去寻找一条 v 的出边使得颜色也是 cu ,假设这条边连向 w ,把这条边置为 cv ,然后再去找 w 的一条出边使得这条出边是 cu ,再置为 cv 就这么一直操作下去。注意,我们寻找的颜色一定是 cu,cv 之一。大致过程长成这样:

image.png

这么一直操作下去,最后一定不会出现环。如果出现了,显然必然是一个偶环。画图一下会发现

image.png

这种情况必然对应着图中的虚线边,这就意味着 cu 并不是一个合法的颜色,或者意味着之前的染色方案并不合法。因此,一定不会找到环。所以按照这样的方式一直染色即可找到一组合法的方案。

最坏情况下,对于每条边可能都需要遍历整张图,复杂度是 O(mn2) 大概,可以通过这个题。

cpp
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
typedef long long ll;
int n , m , k;
int A[MAXN];

pii ed[MAXN];
map<pii,int> M;
int deg[MAXN] , sz[MAXN] , st[MAXN] , cu[MAXN];
vector<pii> G[MAXN];

void doit( int pr , int u , int fd , int go ) {
for( auto& t : G[u] ) if( t.fi == fd ) {
t.fi = go;
doit( u , t.se , go , fd );
}
for( auto& t : G[u] ) if( t.se == pr ) t.fi = fd;
}

int as[MAXN];

void solve() {
cin >> n >> m >> k;
rep( i , 1 , n ) scanf("%*d");
rep( i , 1 , m ) {
int u , v;
scanf("%d%d",&u,&v);
if( u > v ) swap( u , v );
ed[i] = mp( u , v + n );
++ deg[u] , ++ deg[v + n];
}
n = n << 1;
st[0] = 1;
rep( i , 1 , n ) sz[i] = ( deg[i] + k - 1 ) / k , st[i] = st[i - 1] + sz[i - 1];
rep( i , 1 , m ) {
int u = ed[i].fi , v = ed[i].se;
G[st[u]].eb( mp( 0x3f3f3f3f , st[v] ) );
G[st[v]].eb( mp( 0x3f3f3f3f , st[u] ) );
ed[i] = mp( st[u] , st[v] );
M[ed[i]] = i;
++ cu[u] , ++ cu[v];
if( cu[u] == k ) ++ st[u] , cu[u] = 0;
if( cu[v] == k ) ++ st[v] , cu[v] = 0;
}
rep( i , 1 , m ) {
int u = ed[i].fi , v = ed[i].se , fuck = 0 , kcuf = 0;
// cout << u << ' ' << v << endl;
sort( all( G[u] ) ) , sort( all( G[v] ) );
for( int i = 0 ; i < G[u].size() ; ++ i ) if( i + 1 != G[u][i].fi ) {
fuck = i + 1; break;
}
for( int i = 0 ; i < G[v].size() ; ++ i ) if( i + 1 != G[v][i].fi ) {
kcuf = i + 1; break;
}
for( auto& t : G[u] ) if( t.se == v ) t.fi = fuck;
doit( u , v , fuck , kcuf );
}
rep( i , 1 , st[n] ) for( auto t : G[i] ) if( i < t.se ) {
as[M[mp( i , t.se )]] = t.fi;
}
rep( i , 1 , m ) printf("%d\n",as[i]);
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/cf1240f-football/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog