2022杭电多校（七）

2022杭电多校（七）

一、比赛小结 二、题目分析及解法（基础题） 1002、Independent Feedback Vertex Set

题目链接：Problem - 7210 (hdu.edu.cn)

题意：

给你一张特殊的图，你需要将这 n 个点分为两个集合s1, s2，s1 中为独立集合，所有的点不能有边相连；s2中的点不能有环，只能是森林，每个点都有权值，求s1的最大权值和。

题解：

答案必须包含每个三元环中的恰好一个点，因为一个点都不选则会破坏森林约束，选至少两个则会破坏独立集约束。

同时对于一对有至少两个公共点的三元环，确定了答案包含其中一个的某个点之后另一个也随之确定了。

因此答案只可能有三种，分别对应图中唯一的三染色方案（去重后）中的每一种颜色的点。

代码：

#include 
using namespace std;

int main(void) {
  typedef pair pii;
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    vector w(n);
    vector c(n, 0);
    c[0] = 0;
    c[1] = 1;
    c[2] = 2;
    for (int i = 0; i > b;
    int m, M;
    if (l || r)
      m = e + max(l, r);
    else if (b)
      m = e + 1;
    else
      m = e;
    M = e + l + r + min(e + 1, b);
    cout