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

            misschuer

            常用鏈接

            統計

            積分與排名

            百事通

            最新評論

            hdu 2819 Swap

            //做這道題很郁悶, 一開始以為計算行列式值為1.怎么做都不對. 后來發現只需要斜線都為1即可.
            //就會想到二分圖的完全匹配

            #include <iostream>
            #include <queue>
            #define MAXN 105
            using namespace std;

            typedef struct {
                
                int u, v;
            }change;

            int n;
            int re[MAXN][MAXN];
            bool chk[MAXN];
            int match[MAXN];


            int find (int x) {
               
                int i;
                for (i = 1;i <= n;++ i) {
                   
                    if (re[ x ][ i ] && !chk[ i ]) {
                        //若x與i相連,且i不在增廣路上             
                        chk[ i ] = true;
                        if (!match[ i ] || find(match[ i ])) {
                            //若i還沒有匹配,或從i的匹配項有增廣路
                            match[ i ] = x;
                            return 1;
                        }  
                    }
                }  
               
                return 0;
            }

            void init() {

                memset(match , 0 , sizeof(match));
            }

            bool res() {
               
                int i, j, m, k, t;
               
                for(i = 1; i <= n; ++ i) {
                   
                    for(j = 1; j <= n; ++ j) {
                       
                        scanf("%d", &re[ i ][ j ]);
                    }
                }       
               
                init();
                for (i = 1;i <= n;++ i) {          
                   
                    memset(chk , 0 , sizeof(chk));
                    if (!find(i)) return false;
                }
               
                queue<change> Q;
                change p;
               
                for (j = 1; j <= n; ++ j) {
                   
                    m = j;
                    for (k = j; k <= n; ++ k) if (match[ k ] <= match[ m ]) m = k;

                    if (m != j) {
                       
                        p.u = m; p.v = j;
                        Q.push(p);
                        t = match[ m ];
                        match[ m ] = match[ j ];
                        match[ j ] = t;
                    }
                }
               
                printf("%d\n", Q.size());
               
                while(!Q.empty()) {
                   
                    p = Q.front();
                    Q.pop();
                    printf("C %d %d\n", p.u, p.v);
                }
                return true;
            }

            int main() {
               
                while (~scanf("%d", &n)) {
                   
                    if(!res()) puts("-1"); 
                }    
                return 0;
            }

             

            posted on 2011-03-19 20:03 此最相思 閱讀(346) 評論(0)  編輯 收藏 引用

            久久99毛片免费观看不卡| 日日狠狠久久偷偷色综合免费| 成人国内精品久久久久影院VR| 国产精品中文久久久久久久| 99久久综合国产精品二区| 伊人久久无码中文字幕| 久久妇女高潮几次MBA| 久久久WWW成人免费精品| 激情久久久久久久久久| 久久精品视频网| 丁香五月综合久久激情| 国产亚洲美女精品久久久久狼| 精品久久久无码人妻中文字幕豆芽| 日韩人妻无码一区二区三区久久99 | 久久亚洲中文字幕精品有坂深雪| 欧美日韩成人精品久久久免费看| 久久中文精品无码中文字幕| 久久久黄片| 亚洲国产成人久久精品99| 中文字幕无码av激情不卡久久| 污污内射久久一区二区欧美日韩| 亚洲国产成人精品久久久国产成人一区二区三区综 | 国产产无码乱码精品久久鸭| 久久天天躁狠狠躁夜夜96流白浆| 久久综合狠狠综合久久| 久久99精品国产一区二区三区 | 亚洲伊人久久综合中文成人网| 人人狠狠综合久久亚洲高清| 欧美国产成人久久精品| 97久久国产亚洲精品超碰热| 伊人色综合久久天天| 亚洲欧洲精品成人久久奇米网| 久久精品国产亚洲αv忘忧草 | 国产精品久久久天天影视香蕉| 人人狠狠综合久久亚洲| 色诱久久久久综合网ywww| 精品99久久aaa一级毛片| 狠狠综合久久综合88亚洲| 亚洲国产精品久久66| 精品久久久中文字幕人妻| 亚洲国产精品久久久久婷婷软件|