首页 > 代码库 > CF489_B_二分匹配

CF489_B_二分匹配

题目链接:http://codeforces.com/problemset/problem/489/B

题意:给两个数组,将其中对应的绝对值不超过1的数make pair,求最多的pair。

典型的二分匹配水题,比赛的时候脑子发热,写了个极水的,后来写的。。。

代码:

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;#define MAX 202bool flag, visit[MAX];int match[MAX];int cow, stall;int head[MAX];int boy[MAX], girl[MAX];struct edge {    int to, next;} e[MAX*MAX];int index_;void addedge(int u, int v) {    e[index_].to = v;    e[index_].next = head[u];    head[u] = index_;    index_++;}bool dfs(int u) {    int v;    for(int i=head[u]; i!=0; i=e[i].next) {        v = e[i].to;        if(!visit[v]) {            visit[v] = true;            if(match[v]==-1 || dfs(match[v])) {                match[v] = u;                return true;            }        }    }    return false;}int MaxMatch() {    int sum = 0;    memset(match, -1, sizeof(match));    for(int i=1; i<=cow; i++) {        memset(visit, false, sizeof(visit));        if(dfs(i)) sum++;    }    return sum;}int main() {    //freopen("test.txt", "r", stdin);    char ch;    int k, ans, m;    while(scanf("%d", &cow) != EOF) {        memset(head, 0, sizeof(head));        for(int i=1; i<=cow; i++)            scanf("%d", &boy[i]);        scanf("%d", &stall);        for(int i=1; i<=stall; i++)            scanf("%d", &girl[i]);        index_ = 1;        for(int i=1; i<=cow; i++) {            for(int j=1; j<=stall; j++) {                if(abs(boy[i]-girl[j])==1 || boy[i]==girl[j]) addedge(i, j);            }        }        ans = MaxMatch();        printf("%d\n", ans);    }    return 0;}
View Code

 

CF489_B_二分匹配