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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            HDU 2819 Swap 二分圖的最大匹配

            這題的目的是,通過一系列交換,讓矩陣中A[i, i] (1 <= i <= N)的值全為1。
            首先要明確:
            如果某行或者某列全是0。那怎么換都沒辦法的。
            否則,一定能換出來。
            這個動動腦子想一下可以明白的。

            其次要明確:只交換行或者只交換列都是可以換出來的。
            這個動動腦子想一下也可以明白的。

            明確了這兩點,這問題就變成了二分圖的匹配問題。
            二分圖左邊的節點為每一行的行號
            二分圖右邊的節點為每一行中出現的“1”對應的列號
            這樣用匈牙利算法就可以匹配了。

            #include <stdio.h>
            #include 
            <string.h>

            #define NR 128

            int N;
            int mat[NR][NR];
            int res[NR];
            char vis[NR];

            int dfs(int i)
            {
                
            int j;

                
            for (j = 1; j <= N; j++{
                    
            if (mat[i][j] && !vis[j]) {
                        vis[j] 
            = 1;
                        
            if (!res[j] || dfs(res[j])) {
                            res[j] 
            = i;
                            
            return 1;
                        }

                    }

                }


                
            return 0;
            }


            int solve()
            {
                
            int i, j, k, c, t, m;
                
            static int a[NR], b[NR];

                
            for (i = 1; i <= N; i++
                    
            for (j = 1; j <= N; j++
                        scanf(
            "%d"&mat[i][j]);

                memset(res, 
            0sizeof(res));
                
            for (i = 1; i <= N; i++{
                    memset(vis, 
            0sizeof(vis));
                    
            if (!dfs(i))
                        
            return 0;
                }


                c 
            = 0;
                
            for (j = 1; j <= N; j++{
                    m 
            = j;
                    
            for (k = j; k <= N; k++)
                        
            if (res[k] <= res[m])
                            m 
            = k;
                    
            if (m != j) {
                        a[c] 
            = m;
                        b[c] 
            = j;
                        c
            ++;
                        t 
            = res[m];
                        res[m] 
            = res[j];
                        res[j] 
            = t;
                    }

                }


                printf(
            "%d\n", c);
                
            for (i = 0; i < c; i++)
                    printf(
            "C %d %d\n", a[i], b[i]);

                
            return 1;
            }


            int main()
            {
                
            while (scanf("%d"&N) != EOF) 
                    
            if (!solve())
                        printf(
            "-1\n");

                
            return 0;
            }

            posted on 2010-10-25 22:01 糯米 閱讀(916) 評論(1)  編輯 收藏 引用 所屬分類: POJ

            評論

            # re: HDU 2819 Swap 二分圖的最大匹配  回復  更多評論   

            博主,你說
            如果某行或者某列全是0。那怎么換都沒辦法的。
            否則,一定能換出來。
            這個樣例你的程序就是 -1
            3
            1 1 1
            0 1 0
            0 1 0
            2011-11-24 10:59 | tender
            久久国产精品偷99| 国内精品久久久久久久久电影网| 久久夜色精品国产亚洲| 国产成人无码精品久久久久免费| 久久久久高潮毛片免费全部播放 | 久久免费看黄a级毛片| 久久综合五月丁香久久激情| 国产激情久久久久影院老熟女| 青青草国产精品久久久久| 青青草国产精品久久| 国产精品美女久久久久AV福利| 久久久久久亚洲精品不卡| 久久精品一区二区三区中文字幕| 久久久久婷婷| 综合人妻久久一区二区精品| 日韩精品久久久久久久电影蜜臀| 久久久久国产精品熟女影院| 一本一道久久精品综合| 久久伊人色| 久久久精品国产sm调教网站 | 久久精品国产亚洲av高清漫画| 久久棈精品久久久久久噜噜| 99re久久精品国产首页2020| 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲AV日韩精品久久久久久| 国产精品久久网| 久久久久国产一级毛片高清板| 欧美精品丝袜久久久中文字幕 | 色狠狠久久AV五月综合| 97精品国产91久久久久久| A级毛片无码久久精品免费| 久久婷婷色综合一区二区| 亚洲伊人久久精品影院| 久久夜色精品国产亚洲| 久久久久高潮综合影院| 嫩草影院久久99| 亚洲av成人无码久久精品| 久久成人精品| 国产亚洲精品自在久久| 亚洲国产日韩欧美综合久久| 91久久精品91久久性色|