P1041 传染病控制

#include <bits/stdc++.h>

using namespace std;

const int maxn = 301;

std::vector<int> son[maxn];

vector<int> G[maxn];

int deep[maxn], size[maxn];

vector<int> dep[maxn];

int vis[maxn];

int n, p, ans = 0x3f3f3f;

inline void dfs(int f) {

  vector<int>::iterator it;

  size[f] = 1;

  for (it = son[f].begin(); it != son[f].end(); it++) {

    int x = *it;

    deep[x] = deep[f] + 1;

    dfs(x);

    size[f] += size[*it];

  }

}

inline void hit(int root, int state) {

  vector<int>::iterator it;

  if (state == 1)

    vis[root] = 1;

  else

    vis[root] = 0;

  for (it = son[root].begin(); it != son[root].end(); it++) {

    hit(*it, state);

  }

}

inline void search(int d, int now) {

  ans = min(ans, now);

  vector<int>::iterator it;

  for (it = dep[d].begin(); it != dep[d].end(); it++) {

    if (!vis[*it]) {

      hit(*it, 1);

      search(d + 1, now - size[*it]);

      hit(*it, 0);

    }

  }

}

int v[maxn];

inline void trans(int root) {

  v[root] = 1;

  vector<int>::iterator it;

  for (it = G[root].begin(); it != G[root].end(); it++) {

    if (!v[*it]) {

      son[root].push_back(*it);

      trans(*it);

    }

  }

}

inline int read() {

  int x = 0, f = 1;

  char ch = getchar();

  while (ch < '0' || ch > '9') {

    if (ch == '-')

      f = -1;

    ch = getchar();

  }

  while (ch >= '0' && ch <= '9') {

    x = x * 10 + ch - '0';

    ch = getchar();

  }

  return x * f;

}

int main() {

//  freopen("input.in", "r", stdin);

  cin >> n >> p;

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

    int x, y;

    x = read();

    y = read();

    G[x].push_back(y);

    G[y].push_back(x);

  }

  memset(v, 0, sizeof(v));

  trans(1);

  deep[1] = 0;

  dfs(1);

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

    dep[deep[i]].push_back(i);

  }

  search(1, n);

  printf("%d\n", ans);

  return 0;

}