• <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++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              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)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

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

            Feedback

            # re: Maximum Bipartite Matching 2007-12-21 18:22 winsty
            好標準的匈牙利
            贊一個!  回復  更多評論
              

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

            一本一本久久a久久精品综合麻豆| 97精品国产97久久久久久免费| 国产精品禁18久久久夂久| 欧美熟妇另类久久久久久不卡| 99久久成人国产精品免费 | 国产精品日韩欧美久久综合| 2020最新久久久视精品爱| 亚洲国产精品一区二区三区久久 | 亚洲午夜无码AV毛片久久| 一本色道久久99一综合| 久久91亚洲人成电影网站| 亚洲AV伊人久久青青草原| 精品久久无码中文字幕| 亚洲国产精品一区二区三区久久| 精品久久无码中文字幕| 伊人热热久久原色播放www | 欧美黑人激情性久久| 久久www免费人成看国产片| 亚洲AV无码久久精品成人| 久久精品国产亚洲Aⅴ香蕉| 少妇久久久久久被弄高潮| 亚洲国产小视频精品久久久三级| 国产精品一久久香蕉产线看| 久久婷婷色香五月综合激情| 国产精品久久久久一区二区三区| 精品久久久久久无码专区| 国产99久久久国产精品小说| 国产精品成人无码久久久久久 | 日韩中文久久| 久久久网中文字幕| 久久久久一级精品亚洲国产成人综合AV区 | 99久久国产综合精品女同图片| 久久一本综合| 伊人久久大香线蕉AV一区二区| 久久强奷乱码老熟女网站| 国产成人精品综合久久久| 亚洲狠狠久久综合一区77777| 国内精品久久国产大陆| 久久国产精品久久| 久久综合中文字幕| 久久亚洲中文字幕精品一区四|