coreBugZJ

此 blog 已棄。

EOJ 1864 Playing With Cubes

/*
2

EOJ 1864 Playing With Cubes
3

----問題描述：
6

Children are used to playing with special cubes with letters written on the cubes' faces.
8

The goal of the game is to compose words using such cubes.
9

If 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.
12

You 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

----輸入：
17

There are several test cases,
19

each test case begins with two numbers N(1<=N<=50) and M(1<=M<=50).
20

the second line contains N string,the i-th string shows the uppercase letters(between 2 and 50,inclusive) on the i-th cube.
21

The third line contains the M words.Each element of words will contain between 2 and 50 uppercase letters, inclusive.
22

----輸出：
25

Output the words' number that can be composed using the given cubes in ascending order.
27

If no words' number that can be composed output -1.
28

----樣例輸入：
31

5 3
33

ABCDEF DEFGHI OPQRST ZZZZZZ YYYYYY
34

CAT DOG PIZZA
35

6 7
36

ABCDEF DEFGHI OPQRST MNZLSA QEIOGH IARJGS
37

DOG CAT MOUSE BIRD CHICKEN PIG ANIMAL
38

----樣例輸出：
41

1
43

0 1 3 5
44

----分析：
47

對每個 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

求二分圖最大匹配使用匈牙利算法。
55

*/
58

#include <stdio.h>
61

#include <string.h>
62

#define L 59
64

/* 匈牙利算法 begin */
67

int n; /* 一邊 x[0], x[1],

x[n-1] */
69

int m; /* 一邊 y[0], y[1],

y[m-1] */
70

int adj[ L ][ L ]; /* adj[i][j] != 0 表示 x[i] 與 y[j] 有邊 */
71

int res[ L ]; /* res[j] != -1 表示當前與 y[j] 匹配的點為 x[res[j]] */
72

int sta[ L ]; /* sta[j] != 0 表示 y[j] 在可增廣路中 */
73

/* 0 != find 表示找到可增廣路 */
75

int 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

/* 求最大匹配 */
90

int 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

105

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

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1864 Playing With Cubes