记录编号	331110	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.444 s
提交时间	2016-10-27 10:17:41	内存使用	0.32 MiB

//KZNS
#include <cstdio>
#include <vector>
using namespace std;
#define Nmax 303
int N, p;
vector<int> gp[Nmax];
vector<int> Bls[Nmax];
int fa[Nmax];
int deep[Nmax];
int cds[Nmax];
bool lived[Nmax];
void DFS(int x) {
    deep[x] = deep[fa[x]]+1;
    Bls[deep[x]].push_back(x);
    cds[x] = 1;
    int t;
    for (int i = 0; i < gp[x].size(); i++) {
        t = gp[x][i];
        if (fa[x] == t)
            continue;
        fa[t] = x;
        DFS(t);
        cds[x] += cds[t];
    }
}
void init() {
    scanf("%d %d", &N, &p);
    int a, b;
    for (int i = 0; i < p; i++) {
        scanf("%d %d", &a, &b);
        gp[a].push_back(b);
        gp[b].push_back(a);
    }
    DFS(1);
}
int ans = 0;
void CS(int dp, int ln) {
    bool f = true;
    int t;
    for (int i = 0; i < Bls[dp].size(); i++) {
        t = Bls[dp][i];
        if (lived[fa[t]])
            lived[t] = true;
    }
    for (int i = 0; i < Bls[dp].size(); i++) {
        t = Bls[dp][i];
        if (!lived[fa[t]]) {
            lived[t] = true;
            CS(dp+1, ln+cds[t]);
            lived[t] = false;
            f = false;
        }
    }
    for (int i = 0; i < Bls[dp].size(); i++) {
        t = Bls[dp][i];
        if (lived[fa[t]])
            lived[t] = false;
    }
    if (f)
        ans = max(ans, ln);
} 
int main() {
    freopen("epidemic.in", "r", stdin);
    freopen("epidemic.out", "w", stdout);
    init();
    CS(2, 0);
    printf("%d\n", cds[1] - ans);
    return 0;
}
//UBWH