首页 > 代码库 > HDU 2063 最大匹配的基础题

HDU 2063 最大匹配的基础题

中文题,题目大意不说了。

思路:就是寻找最大匹配,最大匹配就是每次找增广路,如果存在增广,那就把增广路上面的边全部都翻转即可。这样说明能多匹配一个,+1即可。

技术分享
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha; printf("haha\n");const int maxn = 500 + 5;vector<int> G[maxn];int n, m, k;int myleft[maxn];bool S[maxn], T[maxn];bool match(int u){    int len = G[u].size();    for (int i = 0; i < len; i++){        int v = G[u][i];        //printf("v = %d\n", v);        if (!T[v]){            T[v] = true;            if (myleft[v] == -1 || match(myleft[v])){                myleft[v] = u;                return true;            }        }    }    return false;}int main(){    while (scanf("%d", &k) && k){        scanf("%d%d", &m, &n);        for (int i = 1; i <= m; i++) G[i].clear();        for (int i = 0; i < k; i++){            int u, v; scanf("%d%d", &u, &v);            G[u].pb(v);        }        memset(S, false, sizeof(S));        memset(T, false, sizeof(T));        memset(myleft, -1, sizeof(myleft));        int ans = 0;        for (int i = 1; i <= m; i++){            memset(T, false, sizeof(T));            if (match(i)) ans++;        }        printf("%d\n", ans);    }    return 0;}
View Code

 

HDU 2063 最大匹配的基础题