C/C++教程

【题解】「COCI 2018.10」Teoreti?ar

本文主要是介绍【题解】「COCI 2018.10」Teoreti?ar，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

题目大意

有一个二分图，构造一种对边的染色方案，使得没有两个颜色相同的边共顶点。

假设对于给定二分图的答案是 \(C\)，记 \(X\) 是大于等于 \(C\) 的最小的 \(2\) 的整次幂，你只需要给出一个方案，使得颜色数量不多于 \(X\)。

\(L, R\le 10^5, m\le 5\times 10^5\)

题解

设度数最大的点的度数为 \(D\)，那么显然答案 \(C\ge D\)，也就是说我们只要构造出一种要颜色数不超过 \(2^{\lceil \log_2 D \rceil}\) 的方案。

假设我们有一个边集 \(E\)，如果每个点的度数都 \(\le 1\)，那么显然此时答案为 \(1\)，否则我们可以考虑把这个边集划分为两个边集 \(E_1, E_2\)，使得每个点的度数尽量被平分，即都不超过 \(\lceil\frac D2\rceil\)。

这样递归下去，可以发现我们就能满足限制了。

边的分割可以跑欧拉回路（其中需要适当加虚点和虚边使得每个点的度数都为偶数）。

时间复杂度 \(O(m\log m)\)。

Code 
#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
const int maxn = 200005;
const int maxm = 500005;
struct Node {
  int x, y, id;
};
int n, m, col, ans[maxm];
std::vector <std::pair <int, int> > edge[maxn];
int lst=2, sz[maxn], Flag[maxm + maxn];
void dfs (int x, int pre=0) {
  while(sz[x]) {
    std::pair <int, int> cur = edge[x].back(); edge[x].pop_back(); -- sz[x];
    if(Flag[cur.second]) continue;
    Flag[cur.second] = 1;
    dfs (cur.first, cur.second);
  } Flag[pre] = lst ^= 1;
}
void solve (std::vector <Node> v) {
  std::vector <int> node;
  for(auto&it:v) {
    ++ sz[it.x]; ++ sz[it.y];
    node.push_back(it.x); node.push_back(it.y);
    edge[it.x].push_back(std::make_pair(it.y, it.id));
    edge[it.y].push_back(std::make_pair(it.x, it.id));
  }
  bool flag = 1;
  for(auto&it:node) if(sz[it] > 1) flag = 0;
  if(flag) {
    ++ col;
    for(auto&it:v) ans[it.id] = col;
    for(auto&it:node) edge[it].clear(), sz[it] = 0;
    return ;
  } int cnt = m;
  for(auto&it:node) if(sz[it]&1) {
    ++ cnt; ++ sz[it]; ++ sz[n + 1];
    edge[it].push_back(std::make_pair(n + 1, cnt));
    edge[n + 1].push_back(std::make_pair(it, cnt));
  } lst = 2; dfs (n + 1);
  for(auto&it:node) dfs (it);
  std::vector <Node> V[2];
  FOR(i,m+1,cnt) Flag[i] = 0;
  for(auto&it:v) {
    V[Flag[it.id] == 2].push_back(it);
    Flag[it.id] = 0;
  }
  solve (V[0]); solve (V[1]);
}
int main (void) {
  int l = read(), r = read(); m = read();
  std::vector <Node> edge; n = l + r;
  FOR(i,1,m) {
    int x = read(), y = read();
    edge.push_back((Node) {x, l + y, i});
  }
  solve (edge);
  printf("%d\n", col);
  FOR(i,1,m) printf("%d\n", ans[i]);
  return 0;
}
这篇关于【题解】「COCI 2018.10」Teoreti?ar的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航