The Way of C++

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  55 Posts :: 0 Stories :: 19 Comments :: 0 Trackbacks

公告

The first time i use this blog, i will write something that i learn which i think is worth write down.

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

   Bipartite graph is the graph which include two sets(name X,and Y) and every edge in the graph has the rule that one point is in X,the other is in  Y. The mostly problem is finding the Maximum Bipartite Matching, which mean find the maximum edges in the case of keeping  the points of the edges only connecting to one edge. The other problem is the perfect matching, which means that all the vector of the graph is included in the match edges. And the solution to find the minimum number of vectors ( either in X and Y) making every edge connecting to these vectors is called the minimum coverage . Usually, we have the equation that " minimum coverage number = maximum bipartite matching". There is another problem called maximum independent set problem. This problem request to find the maximum number of M(the number of vector) which there are no edges connect to in the graph that contain N vectors. This problem can be transformed into the maximum bipartite matching problem if the conditions can be satisfied. And we have the result that " the maximum independent set vector number M= N- Maximum bipartite matching number ".
   One way to solve the maximum bipartite matching problem is the method which is called Hungary Algorithm. There are many problems in the POJ which can be solved by Hungary Algorithm as long as it's a maximum tipartite mathcing or can be transformed into.  As an example ,you can view the problem discription in the link  . The following is my code. (link:  http://acm.pku.edu.cn/JudgeOnline/problem?id=1325)
    Plz forgive my poor written English, but everyone improve it by making mistake and attempting ,right? -_-

 1
 2#include<stdio.h>
 3#include<string.h>
 4#include<iostream>
 5using namespace std;
 6const int MAX= 110;
 7int u,v,k;//u:the left node number,v:the right node number
 8bool c[MAX][MAX];//c[i][j] indicate that i of left connect to the j of right, begin with 0
 9
10int um[MAX],vm[MAX];//um[i] indicate the j of the right that connect to i, they are matched . so is vm[j]
11bool s[MAX];//s[j] check whether j of the right has been used in one round of finding the path
12
13bool Find(int u){
14    int j;
15    for(j=1;j<v;j++){
16        if(c[u][j]&&!s[j]){
17            s[j]=true;
18            if(!vm[j]||Find(vm[j])){
19                um[u]=j;
20                vm[j]=u;
21                return true;
22            }
23        }
24    }
25    return false;
26}
27                
28
29int Match(){
30    memset(um,0,sizeof(um));
31    memset(vm,0,sizeof(vm));
32    int ret=0;
33    int i;
34    for(i=1;i<u;i++)
35        if(!um[i]){
36            memset(s,false,sizeof(s));
37            if(Find(i))
38                ret++;
39        }
40    
41    return ret;
42}
43
44
45int main(){
46    
47    while(scanf("%d%d%d",&u,&v,&k)&&u){
48        memset(c,0,sizeof(c));
49        int i,a,b,d;
50        for(i=0;i<k;i++){
51            scanf("%d%d%d",&a,&b,&d);
52            if(b&&d)
53                c[b][d]=1;
54        }
55        printf("%d\n",Match());
56    }
57    return 1;
58}


   

posted on 2007-12-21 14:53 koson 阅读(1967) 评论(2)  编辑 收藏 引用 所属分类: DataStruct And Algorithm

Feedback

# re: Maximum Bipartite Matching 2007-12-21 18:22 winsty
好标准的匈牙利
赞一个!  回复  更多评论
  

# re: Maximum Bipartite Matching 2007-12-22 11:51 在线软件
不错..
但是我不是很懂啊  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理