首页 > 代码库 > 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;}
CF489_B_二分匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。