2020CCPC冬季营第三日C题：无向图的定向与K着色问题

题目背景

在2020年CCPC Wannafly冬季训练营的第三天比赛中，出现了一道关于无向图定向和K着色的问题。题目要求我们将一个给定的无向图转换成有向图，并确保转化后的图中没有环，同时使最长路径尽可能短。

解决方案

根据题目描述，我们首先了解到，最短的最长路径长度等于该无向图的最小着色数减一。这一结论可以通过迪尔沃斯定理来理解，即在一个偏序集中，最大反链的大小等于最小链划分的数量。在这个问题中，无向图中的顶点可以看作是偏序集中的元素，而颜色则代表不同的链。因此，最小着色数实际上就是将所有顶点划分为不相交的链所需的最少颜色数。
对于如何计算无向图的最小着色数，当数据规模较小时，可以采用状态压缩动态规划（Status Compression Dynamic Programming, SC-DP）或者深度优先搜索（Depth First Search, DFS）的方法进行求解。这两种方法都能有效地找到图的最小着色方案。

代码实现

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
#define ls l, mid, rt <<1
#define rs mid + 1, r, rt <<1 | 1
#define endl '\n'
const int MAXN = 20;
const double EPS = 1e-12;
const ll mod = 1e9 + 7;
map mp;
int T, n, m, now, ans = INT_MAX;
vector G[MAXN], col[MAXN];

// 检查顶点u是否可以被着色为x
bool check(int u, int x) {
    for (auto v : col[x]) {
        if (mp[{v, u}]) return false;
    }
    return true;
}

// 深度优先搜索求解最小着色数
void dfs(int u, int sum) {
    if (u == n + 1) {
        ans = min(ans, sum);
        return;
    }
    if (sum > ans) return;
    for (int i = 1; i <= sum + 1; ++i) {
        if (i == sum + 1) {
            col[++now].push_back(u);
            dfs(u + 1, sum + 1);
            col[now].pop_back();
            --now;
        } else if (check(u, i)) {
            col[i].push_back(u);
            dfs(u + 1, sum);
            col[i].pop_back();
        }
    }
}

int main() {
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        mp[{u, v}] = mp[{v, u}] = true;
    }
    dfs(1, 0);
    cout <    return 0;
}