CF1240F Football

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

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

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

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

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

image.png

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

image.png

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

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

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();
}

\