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

            [轉]zoj 3646 并查集

            Posted on 2012-10-15 21:04 lenohoo 閱讀(380) 評論(0)  編輯 收藏 引用
            轉自小yai
            把b[][]數組上的每個位拆開成兩個點i和i',(不超過32位),另外新加兩個點0和1,如果確定某點i對應的是0,則i與0點合并,i'點與1點合并;如果確定某點i對應的是1,則i與1合并,i'與0合并;如果確定兩點i和j對應的位是相反的數,則i與j'合并,j與i'合并;如果確定兩點對應的位是相同的數,則i與j合并,i'與j'合并。
            最近比較忙,所以題解比較水,所以具體還是看代碼吧。
            因為要空出數給0點和1點,所以我從1到n而不是從0到n-1,所以奇偶性的判斷要換一下。
            #include <cstdio>
            #include <cstring>
            #include <iostream>
            #include <algorithm>
            using namespace std;
            const int maxn = 100000;
            int p[maxn];
            int b[505][505];
            int n;
            void init() {
                for(int i=0;i<(2*n+1)*32+100;i++) p[i] = i;   
            }
            int find(int x) {
                return x==p[x] ? x : p[x] = find(p[x]);   
            }
            void Union(int x,int y) {
                int a = find(x) , b = find(y);
                p[a] = p[b] = p[x] = p[y] = min(a , b);   
            }
            bool check() {
                for(int i=1;i<=n;i++) {
                    for(int j=i+1;j<=n;j++)
                        if(b[i][j] != b[j][i]) return 0;
                    if(b[i][i] != 0) return 0;   
                }
                init();
                int m = 32 * n;
                for(int i=1;i<=n;i++)
                    for(int j=i+1;j<=n;j++) {
                        if(i % 2 == 0 && j % 2 == 0) {
                            for(int k=0;k<32;k++) {
                                if(b[i][j] & (1<<k) == 0) {
                                    int u = i*32+k , v = j*32+k;
                                    if(find(u) == find(1) || find(v) == find(1) || find(u) == find(v+m)) return 0;
                                    Union(u,0);
                                    Union(v,0);
                                    Union(u+m,1);
                                    Union(v+m,1);
                                }   
                            }   
                        }   
                        else if(i % 2 == 1 && j % 2 == 1) {
                            for(int k=0;k<32;k++) {
                                if(b[i][j] & (1<<k)) {
                                    int u = i* 32 + k , v = j*32+k;
                                    if(find(u) == find(0) || find(v)==find(0) || find(u) == find(v+m)) return 0;
                                    Union(u,1);
                                    Union(v,1);
                                    Union(u+m,0);
                                    Union(v+m,0);   
                                }   
                            }   
                        }
                        else {
                            for(int k=0;k<32;k++) {
                                int u = i * 32 + k , v = j * 32 + k;
                                if(b[i][j] & (1<<k)) {
                                    if(find(u) == find(v)) return 0;
                                    Union(u,v+m);
                                    Union(u+m,v);   
                                }
                                else {
                                    if(find(u) == find(v+m)) return 0;
                                    Union(u,v);
                                    Union(u+m,v+m);   
                                }
                            }   
                        }
                    }
                return 1;
            }
            int main() {
                while(~scanf("%d",&n)) {
                    for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                            scanf("%d",&b[i][j]);
                    if(check()) puts("YES");
                    else puts("NO");   
                }
                return 0;   
            }

            posts - 3, comments - 1, trackbacks - 0, articles - 16

            Copyright © lenohoo

            久久久久无码国产精品不卡| 久久人人爽人人爽人人片AV不| 久久亚洲AV成人无码| 精品国产综合区久久久久久| 高清免费久久午夜精品| 国内精品久久久久影院优| 亚洲欧美日韩中文久久| 一本色道久久HEZYO无码| 久久香蕉超碰97国产精品| 99精品久久久久久久婷婷| 亚洲精品乱码久久久久久按摩| 久久久一本精品99久久精品88| 国产亚洲精品久久久久秋霞| 人妻精品久久久久中文字幕一冢本| 国内精品九九久久精品 | 国产99久久精品一区二区| 人妻无码久久一区二区三区免费| 国产精品99久久免费观看| 精品亚洲综合久久中文字幕| 色噜噜狠狠先锋影音久久| 久久久精品国产Sm最大网站| 一级做a爰片久久毛片免费陪| 国产精品乱码久久久久久软件| 超级碰碰碰碰97久久久久| 中文字幕无码精品亚洲资源网久久| 久久综合88熟人妻| 狠狠久久综合伊人不卡| 久久婷婷五月综合成人D啪| 国产情侣久久久久aⅴ免费| 国产成人精品久久综合| 综合久久给合久久狠狠狠97色| 久久综合国产乱子伦精品免费| 伊人久久精品线影院| 久久这里的只有是精品23| 国产午夜精品久久久久免费视| 久久无码精品一区二区三区| 伊人久久大香线蕉av不卡| 91久久香蕉国产熟女线看| 久久综合九色综合网站| 久久免费小视频| 亚洲国产精品无码久久SM|