• <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>

            Better man

            改變性格 改變命運!

             

            圖的最小路徑覆蓋(zoj1525)


            在一個PXP的有向圖中,路徑覆蓋就是在圖中找一些路經,使之覆蓋了圖中的所有頂點,且任何一個頂點有且只有一條路徑與之關聯;(如果把這些路徑中的每條路徑從它的起始點走到它的終點,那么恰好可以經過圖中的每個頂點一次且僅一次);如果不考慮圖中存在回路,那么每每條路徑就是一個弱連通子集.

            由上面可以得出:

            1.一個單獨的頂點是一條路徑;

            2.如果存在一路徑p1,p2,......pk,其中p1 為起點,pk為終點,那么在覆蓋圖中,頂點p1,p2,......pk不再與其它的頂點之間存在有向邊.

            最小路徑覆蓋就是找出最小的路徑條數,使之成為P的一個路徑覆蓋.

            路徑覆蓋與二分圖匹配的關系:

            最小路徑覆蓋=|P|-最大匹配數;

            其中最大匹配數的求法是把P中的每個頂點pi分成兩個頂點pi'與pi'',如果在p中存在一條pi到pj的邊,那么在二分圖P'中就有一條連接pi'與pj''的無向邊;這里pi' 就是p中pi的出邊,pj''就是p中pj 的一條入邊;

            對于公式:最小路徑覆蓋=|P|-最大匹配數;可以這么來理解;

            如果匹配數為零,那么P中不存在有向邊,于是顯然有:

            最小路徑覆蓋=|P|-最大匹配數=|P|-0=|P|;即P的最小路徑覆蓋數為|P|;

            P'中不在于匹配邊時,路徑覆蓋數為|P|;

            如果在P'中增加一條匹配邊pi'-->pj'',那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊,也就是說pi與pj 在一條路徑上,于是路徑覆蓋數就可以減少一個;

            如此繼續增加匹配邊,每增加一條,路徑覆蓋數就減少一條;直到匹配邊不能繼續增加時,路徑覆蓋數也不 能再減少了,此時就有了前面的公式;但是這里只 是說話了每條匹配邊對應于路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊;下面來說明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應于一條匹配 邊;

            與前面類似,對于路徑覆蓋中的每條連接兩個頂點之間的每條有向邊pi--->pj,我們可以在 匹配圖中對應做一條連接pi'與pj''的邊, 顯然這樣做出來圖的是一個匹配圖(這一點用反證法很容易證明,如果得到的圖不是一個匹配圖,那么這個圖中必定存在這樣兩條邊  pi'---pj'' 及 pi' ----pk'',(j!=k),那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ,那邊從pi出發的路徑就不止一條了,這與路徑覆蓋圖是矛盾的;還有另外一種情況就是存在pi'---pj'',pk'---pj'',這種情況也類似可證);

            至此,就說明了匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應關系,那么也就說明了前面的公式成立!

             1 #include <iostream>
             2 using namespace std;
             3 int n,m;
             4 int map[250][250];
             5 bool visit[500];
             6 int l[500];//鄰接點
             7 bool find(int a)
             8 {
             9       for(int i=1;i<=n;++i)
            10             if(map[2*a][2*i-1]&&!visit[2*i-1])
            11             {
            12                   visit[2*i-1]=1;
            13                   if(!l[2*i-1]||find(l[2*i-1]))
            14                   {
            15                         l[2*i-1]=a;
            16                         return true;
            17                   }
            18             }
            19       return false;
            20 }
            21 int main()
            22 {
            23       int cas,a,b;
            24       scanf("%d",&cas);
            25       for(int i=1;i<=cas;++i)
            26       {
            27             memset(l,0,sizeof(l));
            28             memset(map,0,sizeof(map));
            29             scanf("%d%d",&n,&m);
            30             //把節點分成兩個節點,2*i是出節點,2*i-1是如節點
            31             for(int j=1;j<=m;++j)
            32             {
            33                   scanf("%d%d",&a,&b);
            34                   map[2*a][2*b-1]=1;
            35             }
            36             int ans=0;
            37             for(int i=1;i<=n;++i)
            38             {
            39                   memset(visit,0,sizeof(visit));
            40                   if(find(i))ans++;
            41             }
            42             printf("%d\n",n-ans);
            43       }
            44       return 0;
            45 }

            posted on 2009-02-05 14:36 SHFACM 閱讀(1130) 評論(1)  編輯 收藏 引用

            評論

            # re: 圖的最小路徑覆蓋(zoj1525) 2011-03-25 17:12 laoda

            膜拜……
            這個證明我找了好久了……  回復  更多評論   

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲七七久久精品中文国产 | 欧美精品国产综合久久| 精品国产综合区久久久久久| 99久久精品久久久久久清纯| 久久人人爽人人爽人人片AV麻豆 | 日本亚洲色大成网站WWW久久| 91麻精品国产91久久久久| 久久久久久噜噜精品免费直播 | 大香伊人久久精品一区二区| 亚洲伊人久久精品影院| 久久99免费视频| 无码任你躁久久久久久| 国内精品久久久久影院日本| 国产精品女同一区二区久久| 国产69精品久久久久久人妻精品| 国产精品毛片久久久久久久| 热RE99久久精品国产66热| 99999久久久久久亚洲| 天天做夜夜做久久做狠狠| 97久久精品无码一区二区天美| 欧美一级久久久久久久大片| 国产精品久久久久久吹潮| 欧美精品九九99久久在观看| 97精品伊人久久久大香线蕉| 日韩精品久久久肉伦网站| 久久久久国产精品嫩草影院| 精品久久久久久无码专区不卡| 亚洲国产视频久久| 激情综合色综合久久综合| 99久久精品国内| 亚洲国产精品无码久久久蜜芽| 亚洲欧洲精品成人久久奇米网| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久中文字幕人妻熟av女| 久久精品不卡| 国产精品久久久久久久午夜片| 国产V亚洲V天堂无码久久久| 中文字幕日本人妻久久久免费 | 亚洲国产精品无码久久久秋霞2| 久久国产高清一区二区三区| 色综合久久88色综合天天|