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

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热这里只有精品国产免费 | 天天碰免费视频 | 欧美成人在线免费观看 | 台湾亚洲精品一区二区tv | 老师粗又长好猛好爽视频 | 色噜噜国产精品视频一区二区 | 青青草这里只有精品 | 涩涩视频免费观看 | 色拍拍噜噜噜aⅴ在线观看 色拍拍欧美视频在线看 | 四虎影视4hu4虎成人 | aaa级大片 | 毛片在线免费视频 | 天天操天天添 | 九九精品在线播放 | 中国大乳久久 | 日韩欧美手机在线 | 成熟女人50岁一级毛片不卡 | 久久伊人精品综合观看99 | 成人精品视频在线 | 欧美成人精品 | 日韩在线1 | 国产精品一区不卡 | 深夜精品影院18以下勿进 | 国产亚洲精品福利在线 | 新久草在线视频 | 国产精品亚洲欧美日韩区 | 每日更新在线观看av | 国产精品久久久视频 | 久久97精品久久久久久清纯 | 国产中文字幕在线观看 | 国产亚洲欧美日韩在线看片 | 大乳女做爰中文字幕 | 美女精品久久久久久国产潘金莲 | 一级a性色生活片毛片 | 日本在线视频不卡 | 欧美肥婆xxxx欧美另类 | 欧美视频一区二区三区 | 日韩中文字幕精品一区在线 | 亚洲羞羞视频 | 荔枝污| 香蕉久久精品 |