记录编号	43164	评测结果	AAAAAAAAAA
题目名称	[POI 1999] 遗传密码	最终得分	100
用户昵称	codewaysky	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2012-10-07 21:17:50	内存使用	0.34 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int kMaxN = 1000 + 10;

int tree[kMaxN];
int n;
int ind[kMaxN], oud[kMaxN];
bool ok[kMaxN];
bool flag[kMaxN];
int point[kMaxN];
int point_cnt;
int sum[kMaxN];

int Find(int x) {
    if (tree[x] == x) {
        return x;
    } else {
        return tree[x] = Find(tree[x]);
    }
}

void Work() {
    point_cnt = 0;
    for (int i = 1; i <= 1000; i++) {
        if (ok[i]) {
            int v = Find(i);
            if (!flag[v]) {
                flag[v] = true;
                point[++point_cnt] = v;
            }
            sum[v] += abs(ind[i] - oud[i]);
        }
    }

    int ans = n;
    for (int i = 1; i <= 1000; i++) {
        if (flag[i]) {
            if (sum[i] == 0) {          // 当前连通块为欧拉回路时，答案为 n + 1
                ans++;
            } else if (sum[i] == 2) {   // 当前连通块为欧拉道路时，答案为 n + 1
                ans++;
            } else {
                ans += sum[i] / 2 - 1 + 1; // 当前连通块为其他形式时，先构成欧拉道路，再加一，答案为 n + (sum[i]/2 - 1) + 1
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    freopen("pie.in", "r", stdin);
    freopen("pie.out", "w", stdout);

    for (int i = 0; i < kMaxN; i++) {
        tree[i] = i;
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        tree[Find(a)] = Find(b);
        ind[b]++;
        oud[a]++;
        ok[a] = ok[b] = true;
    }

    Work();

    return 0;
}