003

[FarmerLiuAng]

Description

幼儿园准备分糖果给小朋友们, 共有 n 种不同口味的糖果, 编号分别为 1,2,⋯,n, 每种口味只有一个, 每个小朋友可以选择自己最喜欢的两种口味.

现在小朋友们排好队领糖果, 每个小朋友只领他们喜欢的口味的糖果, 如果有小朋友没有领到糖果, 他们就会哭.

请问最少有多少人哭.

Input

输入的第一行包含两个正整数 n∈[2,100000],m∈[1,100000]， 分别表示糖果的数量以及小朋友的人数.

后续 m 行, 每行有两个正整数 a,b∈[1,n]， 表示小朋友喜欢的糖果口味编号.

Output

输出最少多少人哭.

Sample Input 1

4 2 1 3 2 4

Sample Output 1

0

Sample Input 2

10 15 1 2 2 3 3 4 4 5 5 1 1 6 2 7 3 8 4 9 5 10 6 8 7 9 8 10 9 6 10 7

Sample Output 2

6

[dpbnnp]

![Uploading 图片.png…]()

[RonDen]

匈牙利算法

[RonDen]

匈牙利算法求匹配，可以过第一个样例，第二个算得5，裂开了 :sob:

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

using namespace std;
const int N = 200010, M = 200010;
int h[N], e[M], ne[M], idx = 0;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int match[N];
bool vis[N];
int n, m;

bool find(int x) {
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        if (!vis[j]) {
            vis[j] = 1;
            if (!match[j] || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    freopen("2.in", "r", stdin);
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i ++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(n+i, a);
        add(n+i, b);
    }

    int res = 0;
    for (int i = 1; i <= m; i ++) {
        memset(vis, 0, sizeof vis);
        if (find(n+i)) res ++;
    }

    printf("%d\n", m - res);
    return 0;
}

[light-light]

楼上正解。第二个最后只有5个小孩没有分到糖果。可以最大匹配前10个小孩。

[RonDen]

for (int i = 1; i <= n; i ++) {
        printf("(%d->%d)\n", i, match[i]);
}

输出信息为：

(1->15)
(2->11)
(3->12)
(4->13)
(5->14)
(6->16)
(7->17)
(8->18)
(9->19)
(10->20)
5

感觉是没问题的…… :crying_cat_face:

[RonDen]

comment 楼上： 1->15 代表第1个小孩拿到了第5种糖果。后面的数字减10是原始糖果编号。

1->15表示第一个糖果分配给了编号为15的小孩，小孩的编号是从糖果之后开始编号的，见代码n+i。

[weikm]

题目给的第二个样例显然错了，输出就应该等于5呀 我也只能过3个样例【难受】