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

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條評論
主站蜘蛛池模板: 九九资源站 | 久久久无码精品亚洲日韩按摩 | 一区二区三区精品国产 | 国产精品18久久久久久久久久 | 天天狠狠色综合图片区 | 日本激情啪啪 | 男女羞羞网站 | 91视频国产高清 | 国产精品免费观看网站 | 午夜精品福利视频 | 欧美一级特黄乱妇高清视频 | 欧美日屁| 亚洲一级毛片视频 | 殴美一级片 | 色www精品视频在线观看 | 黄色影院在线观看视频 | 91精品久久久久久久久久小网站 | 一本色道久久综合一区 | 国产91在线 | 欧美 | 国产精品久久免费视频 | 久久国产这里只有精品 | 国产精品亚洲欧美日韩一区在线 | 日韩中字在线 | 国产午夜不卡在线观看视频666 | 国产亚洲精品看片在线观看 | 日韩中文字幕在线免费观看 | 久久国产首页 | 天天舔天天舔 | 四虎永久免费网站免费观看 | 四虎 2022 永久网站 | 老司机观看精品一区二区 | 免费视频网站在线观看黄 | 九九热线有精品视频99 | 免费观看一级特黄欧美大片 | 欧美亚洲国产一级毛片 | 国产精品线在线精品国语 | 国产伦精品一区二区三区四区 | 婷婷四房综合激情五月在线 | 久久久久亚洲 | 99最新网址 | 全黄一级裸片视频免费区 |