poj 3041 Asteroids (匈牙利算法---二分图最大匹配)

发布时间:2016-12-11 16:11:19 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3041 Asteroids (匈牙利算法---二分图最大匹配)",主要涉及到poj 3041 Asteroids (匈牙利算法---二分图最大匹配)方面的内容,对于poj 3041 Asteroids (匈牙利算法---二分图最大匹配)感兴趣的同学可以参考一下。

题目:http://poj.org/problem?id=3041 在二分图中,最小点覆盖数=最大匹配数,把光束模型成顶点,小星星模型成连接对应光束的边,这样,等价于求最小点覆盖。 #include<iostream> #include<vector> using namespace std; const int MAXN=501*2; vector<int> G[MAXN]; int N,K; int match[MAXN]; bool used[MAXN]; void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } bool dfs(int v){ used[v]=1; for(int i=0;i<G[v].size();i++){ int u=G[v][i],w=match[u]; if(w<0 || !used[w] && dfs(w)){ match[u]=v; match[v]=u; cout<<u<<" "<<v<<endl; return 1; } } return 0; } int main() { while(cin>>N>>K){ for(int i=0;i<K;i++){ int u,v; cin>>u>>v; add_edge(u,v+N); } int res=0; memset(match,-1,sizeof(match)); for(int v=1;v<=N*2;v++){ if(match[v]<0){ memset(used,0,sizeof(used)); if(dfs(v)) res++; } } cout<<res<<endl; } return 0; } 关于匈牙利算法: 很重要的一个概念就是 增广路(交错路),要明白为什么每次取反之后匹配数会增加一,具体的算法解释自己谷歌吧。

上一篇:Job的提交—客户端
下一篇:常用DIV属性大全(总结)

相关文章

相关评论