2013年8月21日

UVa 11060 - Beverages

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#define PB push_back
using namespace std;


vector<string> words;
map<string, int> indexOf;
bool con[100][100]; 

void find(vector<int> & use, int * cnt) {
  if (use.size() == words.size()) {
    for (int i = 0; i < use.size(); i++) {
      printf("%s%s", words[use[i]].c_str(), i == words.size() - 1 ? ".\n" : " ");
    }
    return;
  }
  for (int i = 0; i < words.size(); i++) {
    if (!cnt[i]) {
      cnt[i] = -1;
      for (int j = 0; j < words.size(); j++) {
        cnt[j] -= con[i][j];
      }
      use.PB(i);
      find(use, cnt);
      return;
    }
  }
}

int main() {
  int N, M, C = 1;
  while (scanf("%d", &N) == 1) {
    char s[99];
    words.clear();
    for (int i = 0; i < N; i++) {
      scanf("%s", s);
      words.PB(s);
      indexOf[s] = i;
    }
    scanf("%d", &M);
    int cnt[100] = {};
    memset(con, false, sizeof(con));
    while (M--) {
      char a[99], b[99];
      scanf("%s%s", a, b);
      int i = indexOf[a], j = indexOf[b];
      if (!con[i][j]) {
        con[i][j] = true;
        cnt[j]++;
      }
    }
    vector<int> use;
    printf("Case #%d: Dilbert should drink beverages in this order: ", C++);
    find(use, cnt);
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言