HDU_2269
唉，一开是理解错了这句话，WA到死……“Then m line follows ,each line contains several things ,which means if these things stay together without the farmer,some thing will been eaten.”这句话的意思是每一行中的若干个东西在农夫不在的时候，不能同时待在一起，而不是说这些东西中任意两者都不能待在一起。
可以用各个二进制位的0、1分别表示每个物品在哪个岸上，再用一个二进制位表示一下农夫现在在哪里，这样总状态并不多，所以直接广搜就行了。
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define MAXD 15 #define ST 2048 #define INF 0x3f3f3f3f char name[MAXD][25]; int N, M, T, f[2][ST], vis[2][ST], danger[ST]; char b[1010]; void init() { int i, j, k, n, st; for(i = 0; i < N; i ++) scanf("%s", name[i]); memset(danger, 0, sizeof(danger)); gets(b); for(i = 0; i < M; i ++) { gets(b); st = 0; char *p = strtok(b, " "); for(j = 0; j < N; j ++) if(strcmp(name[j], p) == 0) st |= 1 << j; while((p = strtok(NULL, " ")) != NULL) for(j = 0; j < N; j ++) if(strcmp(name[j], p) == 0) st |= 1 << j; danger[st] = 1; } } int can(int st) { int i, n = 0; for(i = 0; i < N; i ++) if(st & 1 << i) ++ n; return n <= T; } int check(int st) { for(int i = st; i > 0; i = i - 1 & st) if(danger[i]) return 0; return 1; } void solve() { int i, j, k, cur, st, ans = -1, D = (1 << N) - 1; std::queue <int> q; memset(vis, 0, sizeof(vis)); f[0][0] = 0, vis[0][0] = 1; q.push(0); while(!q.empty()) { cur = q.front() & 1, st = q.front() >> 1, q.pop(); if(cur == 1 && st == D) { ans = f[cur][st]; break; } if(cur == 1 && check(st) && !vis[0][st]) f[0][st] = f[1][st] + 1, vis[0][st] = 1, q.push(st << 1); if(cur == 0) st = ~st & D; for(i = st; i > 0; i = i - 1 & st) if(can(i) && check(st - i)) { if(cur == 0) { int t = ~(st - i) & D; if(!vis[1][t]) f[1][t] = f[0][~st & D] + 1, vis[1][t] = 1, q.push(t << 1 | 1); } else { int t = st - i; if(!vis[0][t]) f[0][t] = f[1][st] + 1, vis[0][t] = 1, q.push(t << 1); } } } printf("%d\n", ans); } int main() { while(scanf("%d%d%d", &N, &M, &T) == 3) { init(); solve(); } return 0; }