UVA 818 - Fany's Blog

Fany's Blog

// UVa818 Cutting Chains
// 陈锋
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>

using namespace std;
// 定义宏，就是为了省一点写循环的工夫。
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)

// 宏
typedef long long LL;

const int MAXN = 16;

/*
    N：总计读入的输入的数量
    VIS：是否被访问过
    DEG：
*/
int N, VIS[MAXN], DEG[MAXN];

// G 是一个数组
unordered_set<int> G[MAXN];
// 每一个环只有两种状态：开和闭
bitset<MAXN> OPEN;

/*
    false 表示有环
    true 表示没有环
    这里用实际的一个例子来想一下就可以想明白了，
    比如，四个环，第一个是开的，后三者缠绕在一起，
    然后代入进去基本就可以理解了
*/
bool dfs(int u, int pa) {
    VIS[u] = -1;
    int d = 0;
    for (auto v : G[u]) {
        if (OPEN[v]) continue;
        if (++d > 2) return false;  // d 是 degree 的意思，表示当前的 u 的度
        if (v != pa) {
            if (VIS[v] == -1) return false;
            if (VIS[v] == 0 && !dfs(v, u)) return false;
        }
    }
    return true;
}

int solve() {
    // 最坏需要打开 N 个环
    int ans = N;
    // 遍历所有的开闭情况
    _for(B, 0, (1 << N)) {
        OPEN.reset();  // 所有位都置 0
        _for(i, 0, N) {
            if (B & (1 << i)) {
                OPEN.set(i);
            }
        }
        int oc = OPEN.count();  // open counts
        int comp = 0;           // 这里的 comp 应是 component 的意思，连通块
        if (oc > ans) {         // 当前的情况如果已经太坏了
            continue;
        }
        bool valid = true;
        // 填充 0
        fill_n(VIS, N, 0);
        _for(u, 0, N) if (!OPEN[u] && !VIS[u]) {
            // 这里其实是相当于最后的 comp 至少为 oc + 2
            // 而如果 comp 为 oc + 2 的时候，那么，oc 会缺一个，导致无法将所有的连通块都连通起来
            if (++comp > oc + 1 || !dfs(u, -1)) {
                valid = false;
                break;
            }
        }
        if (valid) ans = min(ans, oc);  // 这里会对 ans 作出修改
    }
    return ans;
}

int main() {
    // 重定向标准输入
    freopen("./test_cases/uva818.txt", "r", stdin);
    // 每次读入一个 N，并且 N 不为 0，N 是每一行的数据集的环的个数
    for (int t = 1; scanf("%d", &N) == 1 && N; t++) {
        _for(i, 0, N) {
            G[i].clear();  // 将 G 中的 set 都给清空
        }
        int i, j;
        // 每次读入一对连接在一起的节点
        while (scanf("%d%d", &i, &j) == 2 && i > 0 && j > 0) {
            --i, --j;  // 转换成实际的数组中的序号
            // set 里面存放的是与 i 相连的节点，也就是 i 的邻接节点
            G[i].insert(j), G[j].insert(i);
        }
        // 输入完毕开始处理
        int ans = solve();
        printf("Set %d: Minimum links to open is %d\n", t, ans);
    }
    return 0;
}
// 19543127	818	Cutting Chains	Accepted	C++11	0.030	2017-06-19 14:50:27

这里的代码其实写得不好！先看 dfs 这个函数，

// false 表示有环
// 这里用实际的一个例子来想一下就可以想明白了，比如，四个环，第一个是开的，后三者缠绕在一起
bool dfs(int u, int pa) {
  VIS[u] = -1;
  int d = 0;
  for (auto v : G[u]) {
    if (OPEN[v]) continue;
    if (++d > 2) return false; // d 是 degree 的意思，表示当前的 u 的度
    if (v != pa) {
      if (VIS[v] == -1) return false;
      if (VIS[v] == 0 && !dfs(v, u)) return false;
    }
  }
  return true;
}

这里是怎么回事儿呢？这个函数的作用是用来判断连在一起的环有没有串在一起形成一个圆环，按照正常的逻辑，理应是有环返回一个 true，没有环则返回一个 false，而这里的写法则是倒过来了，违反我们常规的写法。另一点则是不应该使用 -1，VIS[u] 这个变量明显是用来判断 u 这个节点有没有被访问过的，那么，我们可以用 1 来表示其被访问过，用 0 来表示其没有被访问过嘛，所以，这里最好是改一下。这样的话，下面的判断语句就可以写得更简洁，

if (VIS[v] == -1)

if (VIS[v])

这样写的话，其目的就一目了然。

然后，看这里的代码，

if (VIS[v] == 0 && !dfs(v, u)) return false;

这里我觉得 && 后面的 !dfs(v, u) 应该和前面的 VIS[v] 分离开来，然后放在这里的 if 语句的代码块里面，然后再进行进一步的判断，会更加容易让人理解。