首页 > 代码库 > hdu1845 Jimmy’s Assignment --- 完备匹配
hdu1845 Jimmy’s Assignment --- 完备匹配
题意:
要求在一个特殊的图上找最大匹配,该图特点是:无向图,每个节点度数为3,是一个边双连通分量(the graph is 2-edge-connected (that is, at least 2 edges need to be removed in order to make the graph disconnected) 这一点是这样理解的把。。)
思路:
一般想法就直接建图求最大匹配,点的范围是5000,不优化可能超时,下面代码是890ms过的。
另一种思路:
完备匹配的条件:
1. G是K(K>0)次正则二分图
2.G是无桥的三次正则图
3.G在去掉任意一个顶点子集S后,其子图中含顶点数为奇数的连通分支数不大于|S|
具有以上三个特征的图一定有完备匹配。且其中第三点是完备匹配的充要条件。
据此可得,题目中所给的图一定是完备匹配,答案是n/2。
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> const int maxn=5010; using namespace std; int main() { int n,a,b,t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<3*n/2;i++) scanf("%d%d",&a,&b); printf("%d\n",n/2); } return 0; }
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> const int maxn=5010; using namespace std; int mx[maxn],my[maxn],n; bool vis[maxn]; vector<int> e[maxn]; int path(int i) { int j,sz=e[i].size(); for(j=0;j<sz;j++) { int tmp=e[i][j]; if(!vis[tmp]) { vis[tmp]=1; if(my[tmp]==-1||path(my[tmp])) { my[tmp]=i; mx[i]=tmp; return 1; } } } return 0; } int hungary() { int res=0; memset(mx,-1,(n+2)*sizeof(int)); memset(my,-1,(n+2)*sizeof(int)); for(int i=1;i<=n;i++) { if(mx[i]==-1) { memset(vis,0,(n+2)*sizeof(vis[0])); res+=path(i); } } return res; } int main() { int T,m,a,b,i; scanf("%d",&T); while(T--) { scanf("%d",&n); m=3*n/2; for(i=1;i<=n;i++) e[i].clear(); while(m--) { scanf("%d%d",&a,&b); e[a].push_back(b); e[b].push_back(a); } printf("%d\n",hungary()/2); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。