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

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视频 | 亚洲精品欧美精品中文字幕 | 就色干综合| 午夜一级免费视频 | 亚洲天堂欧美 | 我就色色综合网 | 亚洲精品美女一区二区三区乱码 | 亚洲 欧美 国产另类首页 | 国产日韩欧美一区二区 | 四虎国产永久在线精品免费观看 | 青青在线精品视频 | 国产成人8x视频一区二区 | 色噜噜五月综合激情久久爱 | 久久久久久久久综合影视网 | 亚洲日本香蕉视频 | 久久久免费视频播放 | 极品吹潮视频大喷潮tv | 久久免费视频7 | 男女拍拍视频黄的全免费 | 国产精品mm| 免费中日高清无专码有限公司 | 亚洲欧美色综合大色 | 人人干人人干 | 久久国产色 | 日本视频播放免费线上观看 | 欧美国产在线观看 | 999成人国产精品 | 在线99热| 国产夜色视频 | 四虎影视在线永久免费观看 | 久久夜色tv网站 | 日韩高清一区 |