• <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對(duì)每個(gè) word 建立二分圖模型，
             49一邊 x[0], x[1],  x[n-1] 分別對(duì)應(yīng) word 中的每個(gè)字母，
             50一邊 y[0], y[1],  y[m-1] 分別對(duì)應(yīng)每個(gè) cube ，
             51若字母 x[i] 包含于 cube y[j] 中，則 x[i] 與 y[j] 連一條邊，
             52然后求出此二分圖最大匹配，若與 word 中字母個(gè)數(shù)相同，則輸出此 word 編號(hào)。
             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 表示當(dāng)前與 y[j] 匹配的點(diǎn)為 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, -1, sizeof(res) );
             93        for ( i = 0; i < n; ++i ) {
             94                memset( sta, 0, sizeof(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, 0, sizeof(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) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久精品国产亚洲av日韩|
777午夜精品久久av蜜臀|
国产福利电影一区二区三区久久久久成人精品综合
|
成人午夜精品久久久久久久小说|
A级毛片无码久久精品免费|
久久久久无码精品国产app|
久久受www免费人成_看片中文|
国产精品一区二区久久国产|
亚洲精品国产成人99久久|
亚洲午夜久久久|
国产精品va久久久久久久|
亚洲精品无码成人片久久|
久久久久亚洲AV无码去区首|
jizzjizz国产精品久久|
国产亚洲精久久久久久无码77777
国产亚洲精品久久久久秋霞
|
久久精品国产第一区二区三区|
久久久久18|
亚洲欧美日韩精品久久|
日产精品久久久久久久性色|
区亚洲欧美一级久久精品亚洲精品成人网久久久久
|
日本久久中文字幕|
久久国产成人午夜aⅴ影院|
av无码久久久久不卡免费网站|
欧美日韩精品久久久久|
亚洲伊人久久综合中文成人网|
91久久精品无码一区二区毛片|
97久久超碰国产精品2021|
久久国产精品无码HDAV|
亚洲人成伊人成综合网久久久|
日韩亚洲国产综合久久久|
国产福利电影一区二区三区，免费久久久久久久精
|
青青青青久久精品国产h久久精品五福影院1421|
久久精品国产亚洲av麻豆小说
|
老司机国内精品久久久久|
.精品久久久麻豆国产精品|
久久丫精品国产亚洲av不卡|
性做久久久久久久|
久久久久久九九99精品|
国产亚洲精久久久久久无码|
久久精品国产精品国产精品污|
99久久精品毛片免费播放|