• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            The Way of C++

              C++博客 :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              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.

            常用鏈接

            留言簿(3)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

               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 閱讀(2217) 評論(2)  編輯 收藏 引用 所屬分類: DataStruct And Algorithm

            Feedback

            # re: Maximum Bipartite Matching 2007-12-21 18:22 winsty
            好標(biāo)準(zhǔn)的匈牙利
            贊一個(gè)!  回復(fù)  更多評論
              

            # re: Maximum Bipartite Matching 2007-12-22 11:51 在線軟件
            不錯(cuò)..
            但是我不是很懂啊  回復(fù)  更多評論
              

            久久亚洲精品人成综合网| 亚洲精品蜜桃久久久久久| 久久青青草原国产精品免费 | 91久久精品91久久性色| 久久亚洲国产中v天仙www| 久久亚洲国产欧洲精品一| 日韩精品无码久久一区二区三| 久久久黄色大片| 大伊人青草狠狠久久| 久久综合久久伊人| 久久国产热精品波多野结衣AV| 久久精品国产亚洲7777| 久久婷婷成人综合色综合| 久久久久久青草大香综合精品| 亚洲AV日韩精品久久久久久| 91秦先生久久久久久久| 久久精品国产亚洲AV麻豆网站| 久久久久久久综合日本| 狠狠久久亚洲欧美专区| 色诱久久久久综合网ywww| 蜜臀久久99精品久久久久久| 亚洲一本综合久久| 99国产欧美久久久精品蜜芽| 一级做a爰片久久毛片毛片| 日韩一区二区久久久久久 | 日韩欧美亚洲综合久久| 国产福利电影一区二区三区,免费久久久久久久精 | 欧美牲交A欧牲交aⅴ久久| 色偷偷88欧美精品久久久| 亚洲国产精品一区二区久久| 潮喷大喷水系列无码久久精品 | 亚洲国产精品久久久天堂 | 国产精品久久久久久久| 久久综合精品国产二区无码| 久久久久国产精品嫩草影院| 亚洲精品无码久久久久AV麻豆| 久久精品一区二区三区中文字幕| 99久久无码一区人妻| 久久精品亚洲福利| 亚洲一区精品伊人久久伊人| 国产精品久久久久免费a∨|