SCU 4439 Vertex Cover|最小点覆盖

传送门

Vertex Cover

frog has a graph with n vertices v(1),v(2),…,v(n)v(1),v(2),…,v(n) and m edges (v(a1),v(b1)),(v(a2),v(b2)),…,(v(am),v(bm))(v(a1),v(b1)),(v(a2),v(b2)),…,(v(am),v(bm)).

She would like to color some vertices so that each edge has at least one colored vertex.

Find the minimum number of colored vertices.

Input

The input consists of multiple tests. For each test:

The first line contains 2 integers n,m (2≤n≤500,1≤m≤n(n−1)/2). Each of the following mm lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi,min{ai,bi}≤30)

Output

For each test, write 11 integer which denotes the minimum number of colored vertices.

Sample Input

    3 2
    1 2
    1 3
    6 5
    1 2
    1 3
    1 4
    2 5
    2 6

Sample Output

    1
    2

题意：有一个n个点m条边组成的图，现在要给点染色，要求每条边最少有一个点被染色，问最少的被染色的点的数量是多少。

题解：很明显是个最小点覆盖问题。

　　　　二分图大讲堂——彻底搞定最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500 + 10;
const int INF = 1<<30;
vector <int> v[N];
int a[N];
bool vis[N];
bool dfs(int x) {
    vis[x] = true;
    for (int i = 0; i < v[x].size(); i++) {
        int y = v[x][i];
        int z = a[y];
        if (!z||(!vis[z]&&dfs(z))) {
            a[x] = y;
            a[y] = x;
            return true;
        }
    }
    return false;
}
int main() {
    int n,m,x,y;
    while (~scanf("%d%d",&n,&m)) {
        for (int i = 0; i <= n; i++) v[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        int ans = 0;
        memset(a,0, sizeof(a));
        for (int i = 1; i <= n; i++) {
            if (!a[i]) {
                memset(vis,false, sizeof(vis));
                if (dfs(i)) ans++;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}