CF1354E Graph Coloring(二分图+背包)

题意:

\(n\) 个点 \(m\) 条边的无向图,对每个点染 \({1,2,3}\) 的颜色,要求使得任意相邻的两个点绝对值之差为 \(1\),且染成 \({1,2,3}\) 颜色的点数分别为 \({n_1,n_2,n_3}\)。

题解:

可以发现点染 \(1\) 或 \(3\) 是等价的,故可以将问题先转化为二分图判定。
注意图不一定是连通的,所以对所有连通块进行二分图判定,如果有一个连通块不是二分图就是 NO。
之后问题就变成,给一个或多个是二分图的连通块,取每个二分图的左部或右部的点(一定要选一边)全部染成 \(2\) 能否刚好染够 \(n_2\)(如果只有左部或右部就是染不染的问题)。
类似于背包,设 \(dp[i][j]\) 表示前 \(i\) 个连通块是否能染 \(j\) 个点为 \(2\)。
转移:用 \(c[i][0/1]\) 表示 \(i\) 连通块左部或右部的大小,则
\(dp[i][j] = 1, if(dp[i-1][j-c[i][0]] == 1)\)
\(dp[i][j] = 1, if(dp[i-1][j-c[i][1]] == 1)\)
当 \(dp[连通块数目][n_2]\) 为 \(1\) 时有解,否则无解。
输出解就是背包记录路径问题。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " is " << x << '\n';
typedef long long LL;

const int N = 5e3 + 5, M = 1e5 + 5, P = 1e9 + 7;

int n, m, n1, n2, n3;
int sz, vis[N], col[N], ans[N], which[N], c[N][2], dp[N][N], who[N][N];
std::vector<int> g[N], r[N][2];

void dfs(int u, int w) {
  vis[u] = 1, col[u] = w, c[sz][w]++;
  r[sz][w].push_back(u);
  for (auto v : g[u]) {
    if (vis[v]) {
      if (col[u] == col[v]) {
        cout << "NO" << '\n';
        exit(0);
      }
    } else {
      dfs(v, w ^ 1);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  cin >> n1 >> n2 >> n3;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      ++sz;
      dfs(i, 0);
    }
  }
  dp[0][0] = 1;
  for (int i = 1; i <= sz; i++) {
    for (int j = n2; j >= 0; j--) {
      if (j - c[i][0] >= 0 && dp[i - 1][j - c[i][0]]) {
        dp[i][j] = 1;
        who[i][j] = 0;
      }
      if (j - c[i][1] >= 0 && dp[i - 1][j - c[i][1]]) {
        dp[i][j] = 1;
        who[i][j] = 1;
      }
    }
  }
  if (!dp[sz][n2]) {
    cout << "NO" << '\n';
  } else {
    for (int i = sz, all = n2; i >= 1; i--) {
      which[i] = who[i][all];
      all -= c[i][who[i][all]];
    }
    for (int i = 1; i <= sz; i++) {
      for (auto v : r[i][which[i]]) ans[v] = 2;
      for (auto v : r[i][which[i] ^ 1]) {
        if (n1) ans[v] = 1, n1--;
        else ans[v] = 3, n3--;
      }
    }
    cout << "YES" << '\n';
    for (int i = 1; i <= n; i++) cout << ans[i];
  }
  return 0;
}
上一篇:预测师的随想系列一:我身边的那些技术厉害的人(who from 微软/亚马逊/谷歌/美团/...)


下一篇:Js的继承方法