• <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++博客 :: 首頁(yè) :: 聯(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ì)

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

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

            Feedback

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

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

            国产高清美女一级a毛片久久w| 日韩精品久久久肉伦网站 | 国产精品女同久久久久电影院| 久久久久久免费一区二区三区| 久久青青国产| 狠狠色丁香婷综合久久| 久久天天躁狠狠躁夜夜2020一| 久久精品中文字幕久久| 久久e热在这里只有国产中文精品99| 亚洲国产精品无码久久SM| 四虎久久影院| 国产精品欧美亚洲韩国日本久久| 亚洲精品国产综合久久一线| 久久高潮一级毛片免费| 久久亚洲日韩看片无码| 亚洲色欲久久久综合网东京热| 久久久久亚洲精品日久生情| 久久成人精品视频| 久久综合狠狠综合久久综合88| 久久久久国产精品麻豆AR影院 | 精品无码人妻久久久久久| 热久久最新网站获取| 亚洲精品高清一二区久久| 国产精品视频久久久| 国产精品久久久久久影院 | 国产一区二区三精品久久久无广告| 亚洲精品久久久www| 精品欧美一区二区三区久久久 | 伊人久久大香线蕉综合5g| 久久国产精品久久| 99久久精品日本一区二区免费| 国产偷久久久精品专区 | 久久无码AV一区二区三区| 久久精品国产一区二区电影| 成人午夜精品久久久久久久小说| 人人狠狠综合久久亚洲婷婷| 久久ww精品w免费人成| 精品久久久久久国产| 久久国产精品99久久久久久老狼| 久久国产精品99精品国产| 久久久久亚洲精品无码蜜桃|