CF141E Clearing Up 题解

思路分析

自认为是一道很好的思维题。

直接看上去的想法是：

跑一个生成树，每一次加的边颜色交替进行，直到拉出生成树。

仔细想想，发现可能无法保证最后是一棵树而不是森林，也是说输出都是 \(-1\) 。

然后，我这个弱智就没有任何思路了。

这时，想起“拖帝”的名言：正难则反。于是考虑先筛去不合法的情况。（以下的判断以并查集为基础）

当 \(n\) 是偶数时，树边个数是 \(n-1\) 一定是奇数，不可能合法，输出 \(-1\)。
我们不管颜色 \(M\) ，把能加入的 \(S\) 色的边加入生成树，记录选入的 \(S\) 色边的条数 \(cnt_1\) 。当 \(cnt_1 < \frac{n-1}{2}\) 时，一定无解。

（因为此时所有的 \(S\) 能加入的都加入了，真实情况只少不多，此时都没到一半，就不可能了。）
把 \(M\) 色边能加入的加入生成树，并记录 \(cnt_2\) 。如果 \(cnt_1 + cnt_2 < n-1\) 一定无解。

（同样 \(M\) 色的边能加的都加上去了，在所需最少的情况下全部加完都不够，不可能有解。）
先还原，然后再扫一遍，类似第二步，把 \(S\) 色改成 \(M\) 色即可。（当 \(cnt_2=\frac{n-1}{2}\) 时有解停止。）

思路就是这样，然后直接把 \(S\) 还原即可。

Code

#include <bits/stdc++.h>

#define file(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

#define quad putchar(' ')

#define Enter putchar('\n')

const int N = 100005;

int n, m, fa[N], tot, cnt1, cnt2, visit[N], ans[N];

struct Node {

  int x, y, col;

  Node (int _x = 0, int _y = 0, int _col = 0) {x = _x; y = _y; col = _col;}

}node[N];

namespace UFS {

inline void init();

inline int find(int x);

}

using UFS::find;

signed main(void) {

//  file("CF141E");

  std::cin >> n >> m;

  if (n % 2 == 0) {

    printf("-1");

    return 0;

  }

  for (int i = 1, x, y; i <= m; i++) {

    scanf("%d %d", &x, &y);

    char c[4];

    scanf("%s", c + 1);

    if (c[1] == 'S')

      node[++tot] = Node(x, y, 1);

    else

      node[++tot] = Node(x, y, 2);

  }

  UFS::init();

  for (int i = 1; i <= m; i++) {

    int x, y;

    if (node[i].col == 2) continue;

    x = node[i].x, y = node[i].y;

    x = find(x); y = find(y);

    if (x == y) continue;

    fa[x] = y;

    cnt1 ++;

  }

  if (cnt1 < (n - 1) / 2) {

    printf("-1");

    return 0;

  }

  for (int i = 1; i <= m; i++) {

    int x, y;

    if (node[i].col == 1) continue;

    x = node[i].x, y = node[i].y;

    x = find(x); y = find(y);

    if (x == y) continue;

    fa[x] = y; visit[i] = 1;

    cnt2 ++;

    ans[i] = 1;

  }

  if (cnt1 + cnt2 < n - 1) {

    printf("-1");

    return 0;

  }

  UFS::init();

  for (int i = 1; i <= m; i++) {

    int x, y;

    if (node[i].col == 1) continue;

    if (visit[i] == 0) continue;

    x = node[i].x, y = node[i].y;

    x = find(x); y = find(y);

    if (x == y) continue;

    fa[x] = y;

  }

  for (int i = 1; i <= m; i++) {

    int x, y;

    if (node[i].col == 1) continue;

    if (visit[i] == 1) continue;

    x = node[i].x, y = node[i].y;

    x = find(x); y = find(y);

    if (x == y) continue;

    fa[x] = y;

    cnt2++;

    ans[i] = 1;

    if (cnt2 == (n - 1) / 2) break;

  }

  if (cnt2 < (n - 1) / 2) {

    printf("-1");

    return 0;

  }

  for (int i = 1; i <= m; i++) {

    int x, y;

    if (node[i].col == 2) continue;

    x = node[i].x, y = node[i].y;

    x = find(x); y = find(y);

    if (x == y) continue;

    fa[x] = y;

    ans[i] = 1;

  }

  printf("%d\n", n - 1);

  for (int i = 1; i <= m; i++)

    if (ans[i]) printf("%d ", i);

}

namespace UFS {

inline void init() {

  for (int i = 1; i <= n; i++)

    fa[i] = i;

}

inline int find(int x) {

  if (x == fa[x]) return x;

  return fa[x] = find(fa[x]);

}

}

巴特西

CF141E Clearing Up 题解

思路分析

Code

最新文章

热门文章