• <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
            亚洲中文字幕无码一久久区| 欧美亚洲日本久久精品| 久久精品亚洲日本波多野结衣| 潮喷大喷水系列无码久久精品| 一本色道久久88加勒比—综合| 日韩久久无码免费毛片软件 | 久久无码人妻一区二区三区午夜| 久久久婷婷五月亚洲97号色| 国产精品丝袜久久久久久不卡| 久久无码AV中文出轨人妻| 久久99国产综合精品免费| 亚洲精品无码久久久| 久久er国产精品免费观看2| 性高湖久久久久久久久AAAAA| 国产美女久久久| 久久天天躁狠狠躁夜夜网站| 日韩十八禁一区二区久久| 日本免费一区二区久久人人澡 | 91久久精品国产成人久久| 久久久久久免费视频| 国产精品丝袜久久久久久不卡| 热re99久久精品国99热| 久久强奷乱码老熟女网站| 久久久久久亚洲精品无码| 久久九九青青国产精品| 久久99国产精品尤物| 亚洲午夜久久久影院| 人妻中文久久久久| 亚洲?V乱码久久精品蜜桃 | 国产精品久久久久久久久免费 | 久久人人爽人人精品视频| 久久99国产精品久久99| 久久精品aⅴ无码中文字字幕不卡| 亚洲伊人久久综合中文成人网| 精品国产一区二区三区久久蜜臀 | 欧美麻豆久久久久久中文| 精品水蜜桃久久久久久久| 99久久国产综合精品网成人影院 | 久久人人超碰精品CAOPOREN| 久久久久亚洲AV无码去区首| 久久综合色区|