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

            coreBugZJ

            此 blog 已棄。

            EOJ 1864 Playing With Cubes

              1/*
              2EOJ 1864 Playing With Cubes
              3
              4
              5----問題描述:
              6
              7Children are used to playing with special cubes with letters written on the cubes' faces.
              8The goal of the game is to compose words using such cubes.
              9If you want to compose the word "DOG", you must find 3 cubes, one containing the letter 'D',
             10        one containing the letter 'O', and one containing the letter 'G',
             11        and orient them so the proper letters are facing upward.
             12You are also given a some words, 
             13        each element of which contains a word that you would like to spell out using the cubes.
             14
             15
             16----輸入:
             17
             18There are several test cases,
             19each test case begins with two numbers N(1<=N<=50) and M(1<=M<=50).
             20the second line contains N string,the i-th string shows the uppercase letters(between 2 and 50,inclusive) on the i-th cube.
             21The third line contains the M words.Each element of words will contain between 2 and 50 uppercase letters, inclusive.
             22
             23
             24----輸出:
             25
             26Output the words' number that can be composed using the given cubes in ascending order.
             27If no words' number that can be composed output -1.
             28
             29
             30----樣例輸入:
             31
             325 3
             33ABCDEF DEFGHI OPQRST ZZZZZZ YYYYYY
             34CAT DOG PIZZA
             356 7
             36ABCDEF DEFGHI OPQRST MNZLSA QEIOGH IARJGS
             37DOG CAT MOUSE BIRD CHICKEN PIG ANIMAL
             38
             39
             40----樣例輸出:
             41
             421
             430 1 3 5
             44
             45
             46----分析:
             47
             48對每個 word 建立二分圖模型,
             49一邊 x[0], x[1],  x[n-1] 分別對應 word 中的每個字母,
             50一邊 y[0], y[1],  y[m-1] 分別對應每個 cube ,
             51若字母 x[i] 包含于 cube y[j] 中,則 x[i] 與 y[j] 連一條邊,
             52然后求出此二分圖最大匹配,若與 word 中字母個數相同,則輸出此 word 編號。
             53
             54求二分圖最大匹配使用匈牙利算法。
             55
             56
             57*/

             58
             59
             60#include <stdio.h>
             61#include <string.h>
             62
             63#define  L  59
             64
             65
             66/* 匈牙利算法 begin */
             67
             68int n;             /* 一邊 x[0], x[1],  x[n-1] */
             69int m;             /* 一邊 y[0], y[1],  y[m-1] */
             70int adj[ L ][ L ]; /* adj[i][j] != 0  表示 x[i] 與 y[j] 有邊 */
             71int res[ L ];      /* res[j]    != -1 表示當前與 y[j] 匹配的點為 x[res[j]] */
             72int sta[ L ];      /* sta[j]    != 0  表示 y[j] 在可增廣路中 */
             73
             74        /* 0 != find 表示找到可增廣路 */
             75int find( int i ) {
             76        int j;
             77        for ( j = 0; j < m; ++j ) {
             78                if ( adj[ i ][ j ] && (! sta[ j ]) ) {
             79                        sta[ j ] = 1;
             80                        if ( (-1 == res[ j ]) || (find(res[j])) ) {
             81                                res[ j ] = i;
             82                                return 1;
             83                        }

             84                }

             85        }

             86        return 0;
             87}

             88
             89        /* 求最大匹配 */
             90int maxMatch() {
             91        int i, ans = 0;
             92        memset( res, -1sizeof(res) );
             93        for ( i = 0; i < n; ++i ) {
             94                memset( sta, 0sizeof(sta) );
             95                if ( find(i) ) {
             96                        ++ans;
             97                }

             98        }

             99        return ans;
            100}

            101
            102/* 匈牙利算法 end */
            103
            104
            105int main() {
            106        int  tc, tw;
            107        char cube[ L ][ L ];
            108        char word[ L ];
            109        int  ans[ L ], tot;
            110        int  i, j, k;
            111        while ( 2 == scanf( "%d%d"&tc, &tw ) ) {
            112                tot = 0;
            113
            114                for ( i = 0; i < tc; ++i ) {
            115                        scanf( "%s", cube[ i ] );
            116                }

            117                for ( i = 0; i < tw; ++i ) {
            118                        scanf( "%s", word );
            119
            120                        memset( adj, 0sizeof(adj) );
            121                        n = strlen( word );
            122                        m = tc;
            123                        for ( j = 0; j < n; ++j ) {
            124                                for ( k = 0; k < m; ++k ) {
            125                                        if ( strchr( cube[ k ], word[ j ] ) != NULL ) {
            126                                                adj[ j ][ k ] = 1;
            127                                        }

            128                                }

            129                        }

            130
            131                        if ( maxMatch() == n ) {
            132                                ans[ tot++ ] = i;
            133                        }

            134                }

            135
            136                if ( 0 == tot ) {
            137                        puts( "-1" );
            138                        continue;
            139                }

            140                printf( "%d", ans[ 0 ] );
            141                for ( i = 1; i < tot; ++i ) {
            142                        printf( " %d", ans[ i ] );
            143                }

            144                puts( "" );
            145        }

            146        return 0;
            147}

            148

            posted on 2012-03-30 22:16 coreBugZJ 閱讀(750) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

            久久男人AV资源网站| 久久99精品国产麻豆宅宅| 久久se精品一区二区| 久久99国产综合精品| 日本一区精品久久久久影院| 久久AⅤ人妻少妇嫩草影院| 狠狠色丁香久久婷婷综合图片| 久久国产AVJUST麻豆| 久久精品www人人爽人人| 久久久久婷婷| 久久久久四虎国产精品| 污污内射久久一区二区欧美日韩| 粉嫩小泬无遮挡久久久久久| 久久九九久精品国产| 亚洲精品乱码久久久久久久久久久久| 四虎国产永久免费久久| 久久综合亚洲鲁鲁五月天| 成人精品一区二区久久久| 国产亚洲美女精品久久久久狼| 久久精品国产72国产精福利| 久久影院综合精品| 人妻无码αv中文字幕久久| 久久九色综合九色99伊人| 国内精品久久久久久野外| 无码精品久久久天天影视| 亚洲精品乱码久久久久久蜜桃| 久久久久99精品成人片三人毛片 | 久久亚洲精品视频| 日韩人妻无码精品久久免费一| 亚洲AV伊人久久青青草原| 久久久精品视频免费观看| 久久久久国产一级毛片高清板| 99久久无色码中文字幕| 精品99久久aaa一级毛片| 亚洲国产精品一区二区久久| AA级片免费看视频久久| 久久美女网站免费| 中文字幕亚洲综合久久2| 亚洲国产精品久久久久久| 久久亚洲国产午夜精品理论片| 99久久亚洲综合精品成人|