青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(768) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产美女在线精品免费观看| 国产美女诱惑一区二区| 亚洲国产99| 亚洲第一福利视频| 免费日韩av| 夜夜爽99久久国产综合精品女不卡| 欧美激情中文字幕在线| 欧美sm重口味系列视频在线观看| 亚洲高清久久| 日韩一区二区免费看| 国产精品成人免费| 久久久久.com| 免费影视亚洲| 亚洲一区一卡| 午夜久久久久久| 亚洲国产成人tv| 日韩西西人体444www| 国产日韩欧美在线播放| 免费不卡在线观看| 欧美日韩高清一区| 久久久99国产精品免费| 欧美成人精品在线| 午夜精品在线视频| 久久综合久久久久88| 在线综合欧美| 久久久精品网| 亚洲一区二区视频在线观看| 久久精品国产在热久久| 一区二区欧美视频| 久久国产精品久久久久久久久久 | 欧美激情导航| 亚洲专区免费| 久热精品视频在线| 欧美在线亚洲综合一区| 久久不射2019中文字幕| 日韩小视频在线观看专区| 亚洲永久精品国产| 亚洲日本免费| 欧美亚洲免费电影| 亚洲午夜成aⅴ人片| 久久精品国产999大香线蕉| 夜久久久久久| 久久亚洲影院| 久久久免费精品视频| 欧美日韩视频免费播放| 欧美成年人视频| 国产九区一区在线| 一本色道婷婷久久欧美| 亚洲黄色高清| 久久综合五月天婷婷伊人| 午夜精品美女自拍福到在线| 欧美猛交免费看| 欧美成人精品三级在线观看| 国产午夜精品一区二区三区视频| 91久久视频| 亚洲激情二区| 老司机精品视频网站| 久久久久久久尹人综合网亚洲 | 裸体素人女欧美日韩| 欧美中文字幕视频在线观看| 欧美日韩ab片| 亚洲精品国产精品国自产观看浪潮 | 久久久99久久精品女同性 | 国产日韩欧美不卡| 亚洲一区二区免费| 亚洲欧美影院| 国产精品精品视频| 正在播放欧美视频| 性感少妇一区| 国产欧美日韩一区二区三区在线 | 亚洲欧美日韩国产综合| 亚洲一区二区三区在线观看视频 | 久久久在线视频| 久久中文在线| 国产亚洲毛片在线| 久久久久久精| 国产精品扒开腿爽爽爽视频| 亚洲精品男同| 亚洲午夜在线视频| 亚洲女与黑人做爰| 一本大道久久a久久精二百| 欧美女同在线视频| 久久99在线观看| 在线一区视频| 亚洲激情精品| 蜜臀av国产精品久久久久| 亚洲欧美一区二区三区极速播放| 亚洲欧洲在线观看| 精品av久久久久电影| 国产精品入口尤物| 欧美日韩国产页| 欧美成人69av| 久久视频精品在线| 久久精品欧美| 欧美一区二区三区免费观看| 亚洲午夜精品网| 一本一道久久综合狠狠老精东影业| 欧美国产亚洲视频| 欧美88av| 女人色偷偷aa久久天堂| 久久综合网色—综合色88| 久久国产视频网| 久久成人免费视频| 久久狠狠亚洲综合| 欧美中文日韩| 久久久久国产一区二区三区四区| 欧美一区亚洲| 久久久精品国产一区二区三区| 欧美一区二区高清在线观看| 亚洲自拍电影| 欧美一级二区| 久久精精品视频| 久久精品卡一| 久久在线播放| 欧美高清hd18日本| 91久久综合| 夜夜精品视频| 亚洲色诱最新| 亚洲欧美成人一区二区在线电影| 亚洲影音一区| 欧美一区1区三区3区公司| 欧美中文在线观看国产| 久久亚洲影音av资源网| 免费亚洲视频| 欧美视频在线免费看| 欧美视频在线看| 国产日韩欧美在线播放不卡| 狠狠色丁香婷婷综合久久片| 在线色欧美三级视频| 亚洲精品一区中文| 亚洲特黄一级片| 久久国内精品视频| 欧美激情2020午夜免费观看| 最新高清无码专区| 亚洲欧美在线x视频| 久久久久成人精品免费播放动漫| 欧美成人午夜77777| 欧美性天天影院| 狠狠综合久久av一区二区老牛| 亚洲国产精品一区二区第四页av| 在线综合亚洲欧美在线视频| 久久精品一区中文字幕| 亚洲国产日韩美| 亚洲一级特黄| 免费不卡在线视频| 国产精品美女诱惑| 亚洲国产精品美女| 亚洲欧美日韩在线一区| 欧美xxx成人| 亚洲视频播放| 久色婷婷小香蕉久久| 国产精品v亚洲精品v日韩精品 | 亚洲香蕉网站| 久久免费国产精品1| 日韩视频国产视频| 久久精品国产欧美亚洲人人爽| 欧美喷潮久久久xxxxx| 狠狠v欧美v日韩v亚洲ⅴ| 99re热这里只有精品视频| 久久久天天操| 国产精品99久久久久久久久久久久 | 亚洲国产老妈| 欧美在线影院| 国产精品爱啪在线线免费观看| 亚洲第一色在线| 欧美中文字幕久久| 一个色综合av| 欧美国产精品日韩| 激情视频一区二区三区| 午夜精品久久久久影视| 亚洲三级国产| 欧美成人综合一区| 伊人久久久大香线蕉综合直播 | 久久精品亚洲国产奇米99| 一片黄亚洲嫩模| 欧美成人中文| 亚洲国产精品成人精品| 久久久91精品国产一区二区精品| 中日韩美女免费视频网址在线观看| 欧美.日韩.国产.一区.二区| 韩国精品在线观看| 久久精品一区中文字幕| 亚洲综合欧美| 国产精品一区二区三区乱码| 亚洲午夜成aⅴ人片| 亚洲免费观看高清在线观看 | 国产精品国产三级欧美二区 | 亚洲女ⅴideoshd黑人| 亚洲精品一二| 欧美激情1区| 日韩亚洲欧美综合| 亚洲国产91精品在线观看| 麻豆久久精品| 91久久夜色精品国产九色| 欧美国产1区2区| 欧美a一区二区| 日韩亚洲欧美高清| 日韩视频一区二区在线观看 | 欧美精品在线视频观看| 99在线精品观看|