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$ 的一对还没有用过的颜色 $c_u,c_v$ 。如果有 $c_u = c_v$ ,显然可以直接给这条边染色。否则,我们把这条边置为 $c_u$ ,然后去寻找一条 $v$ 的出边使得颜色也是 $c_u$ ,假设这条边连向 $w$ ,把这条边置为 $c_v$ ,然后再去找 $w$ 的一条出边使得这条出边是 $c_u$ ,再置为 $c_v$ $\dots$ 就这么一直操作下去。注意,我们寻找的颜色一定是 $c_u,c_v$ 之一。大致过程长成这样:

image.png

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

image.png

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

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

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/2021/03/21/cf1240f-football/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog