首页 > 代码库 > ural 1109,NYOJ 239,匈牙利算法邻接表
ural 1109,NYOJ 239,匈牙利算法邻接表
NYOJ 239：http://acm.nyist.net/JudgeOnline/problem.php?pid=239
ural 1109 :http://acm.timus.ru/problem.aspx?space=1&num=1109
NYOJ 月老的难题，是裸的最大匹配，很烦的是邻接阵超时。改用邻接表。
#include <bits/stdc++.h>using namespace std;#define maxn 1005vector <int> G[maxn];bool use[maxn];int match[maxn];int m,n,k;bool dfs(int u){ for(int i=0;i<G[u].size();i++) { if(use[G[u][i]]==false) { use[G[u][i]] = true; if(match[G[u][i]]==-1||dfs(match[G[u][i]])) { match[G[u][i]] = u; return true; } } } return false;}int main(){ scanf("%d%d%d",&m,&n,&k); for(int i=0;i<k;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } memset(match,-1,sizeof(match)); int ans = 0; for(int i=1;i<=m;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans ++; } printf("%d\n",ans); //printf("%d\n",m+n-ans); return 0;}
然后是ural,最小路径覆盖。
题意：
A国家有M个代表，B国有N个代表，其中有K对代表可以进行谈判（一个是A国的，一个是B国的），并且每一个代表至少被包含在其中一对中（也就是说，每个 人可以至少找到另外一个人谈判），每一对谈判需要一对电话联系（一对电话联系数目算1），现在使每个人都能进行电话联系的最少联系数目。
就是求最少对数。每个点都要有边相连，这样的边最少是多少——最小路径覆盖。
首先求一下最大匹配(都是一对一)，可能还有没有匹配的人，加上这些人，如案例： 最大匹配2，还有左边2号没有匹配。加上这个人。
得公式：
最小路径覆盖 = n+ m - 2 * ans + ans;
#include <bits/stdc++.h>using namespace std;#define maxn 1005vector <int> G[maxn];bool use[maxn];int match[maxn];int m,n,k;bool dfs(int u){ for(int i=0;i<G[u].size();i++) { if(use[G[u][i]]==false) { use[G[u][i]] = true; if(match[G[u][i]]==-1||dfs(match[G[u][i]])) { match[G[u][i]] = u; return true; } } } return false;}int main(){ scanf("%d%d%d",&m,&n,&k); for(int i=0;i<k;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } memset(match,-1,sizeof(match)); int ans = 0; for(int i=1;i<=m;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans ++; } printf("%d\n",m+n-ans); return 0;}
ural 1109,NYOJ 239,匈牙利算法邻接表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。