亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

poj2594 Treasure Exploration 二分匹配之最小

系統(tǒng) 1715 0

http://poj.org/problem?id=2594

太經(jīng)典了,最小路徑覆蓋之變形!如果題目中有暗示此圖無環(huán)且路徑是單向的話,必然是最小路徑覆蓋無疑!
這個題的題目意思和那個傘兵題差不多,但是傘兵走過的路徑是可以交叉的, 這樣我們先做一個傳遞閉包,然后再連邊做最小路徑覆蓋即可。

Source Code

Problem: 2594 ? User: 541780774
Memory: 652K ? Time: 1110MS
Language: G++ ? Result: Accepted


Source Code

    #include<stdio.h>   #include<stdlib.h>   #include<string.h>      int nx, ny;             // X的點(diǎn)數(shù)目、Y的點(diǎn)數(shù)目    int mx[501], my[501];   // X各點(diǎn)的配對對象、Y各點(diǎn)的配對對象    bool vy[501];           // 紀(jì)錄Graph Traversal拜訪過的點(diǎn)    bool adj[501][501];     // 精簡過的adjacency matrix       // 以DFS建立一棵交錯樹    bool DFS(int x)    {        for (int y=0; y<ny; ++y)            if (adj[x][y] && !vy[y])            {                vy[y] = true;                   // 找到擴(kuò)充路徑                  if (my[y] == -1 || DFS(my[y]))                {                   mx[x] = y; my[y] = x;                   return true;                   }            }        return false;    }       int bipartite_matching()    {        // 全部的點(diǎn)初始化為未匹配點(diǎn)。        memset(mx, -1, sizeof(mx));           memset(my, -1, sizeof(my));           // 依序把X中的每一個點(diǎn)作為擴(kuò)充路徑的端點(diǎn),        // 並嘗試尋找擴(kuò)充路徑。        int c = 0;        for (int x=0; x<nx; ++x)   //     if (mx[x] == -1)    // x為未匹配點(diǎn),這行可精簡。            {                // 開始Graph Traversal                memset(vy, false, sizeof(vy));                if (DFS(x)) c++;            }        return c;    }   void Floyd(int n)   {           int i,j,k;           for(k=0;k<n;k++)           for(i=0;i<n;i++)           for(j=0;j<n;j++)           {              if(i!=j&&adj[i][k]&&adj[k][j])              adj[i][j]=1;           }       }              main()   {            int i,a,b,n,m;            while(scanf("%d%d",&n,&m),n!=0||m!=0)            {               memset(adj, 0, sizeof(adj));                for(i=0;i<m;i++)               {                scanf("%d%d",&a,&b);                adj[a-1][b-1]=1;               }               Floyd(n);               nx=ny=n;               printf("%d\n",n-bipartite_matching());            }            system("pause");   }        
  

poj2594 Treasure Exploration 二分匹配之最小路徑覆蓋+傳遞閉包


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲国产福利精品一区二区 | 色婷婷在线播放 | 最近中文字幕在线 | 中文 | 国产欧美日韩在线播放 | 夜夜夜夜夜夜夜猛噜噜噜噜噜噜 | 99久久99热久久精品免 | 日本高清不卡免费 | 国产另类图片 | 欧美精品亚洲精品日韩一区 | 欧美视频在线观看 | 热er99久久6国产精品免费 | 91久久在线 | 写真福利 第 页 在线视频 | 国产激情视频在线 | 久草免费公开视频 | 久久人人澡 | 日本九九视频 | 日本成人一区二区 | 91精品免费高清在线 | 国产高清在线观看麻豆 | 97影院午夜午夜伦不卡 | 亚洲播放 | 最新精品亚洲成a人在线观看 | 96精品视频在线播放免费观看 | 午夜a毛片| 国产成人亚洲欧美三区综合 | 在线观看国产精品日本不卡网 | 男人天堂黄色 | 久久98 | www.欧美精品 | 青青青在线观看免费视频精品 | 欧美日韩精品一区二区三区 | 成人欧美在线观看免费视频 | 伊人久久综合影院 | 国产好大好爽久久久久久久 | 国产高清视频在线播放 | 视频播放在线观看精品视频 | 老妇女性较大毛片 | 亚洲 欧洲 自拍 另类 校园 | 在线有码| 九九久久精品国产 |