Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <sstream>
- #include <cassert>
- #include <memory.h>
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <map>
- #include <algorithm>
- #include <string>
- #include <set>
- using namespace std;
- typedef long long ll;
- const int maxn = 11111;
- int n, m;
- int k;
- vector<int> e[maxn];
- int mt[maxn], tm[maxn];
- int when[maxn], tmr;
- bool dfs(int v) {
- if (when[v] == tmr) return 0;
- when[v] = tmr;
- for (int i = 0; i < (int)e[v].size(); i++) {
- int to = e[v][i];
- if (mt[to] == -1) {
- tm[v] = to;
- mt[to] = v;
- return 1;
- }
- }
- for (int i = 0; i < (int)e[v].size(); i++) {
- int to = e[v][i];
- if (dfs(mt[to])) {
- tm[v] = to;
- mt[to] = v;
- return 1;
- }
- }
- return 0;
- }
- int main() {
- freopen("sociology.in", "r", stdin);
- freopen("sociology.out", "w", stdout);
- int test = 0;
- while (scanf("%d%d", &m, &n) == 2) {
- memset(mt, -1, sizeof(mt));
- memset(tm, -1, sizeof(tm));
- for (int i = 0; i < n; i++) {
- e[i].clear();
- }
- scanf("%d", &k);
- for (int i = 0; i < k; i++) {
- int a, b;
- scanf("%d%d", &a, &b);
- e[--b].push_back(--a);
- }
- /*for (int i = 0; i < n; i++) {
- for (int j = 0; j < (int)e[i].size(); j++) {
- if (mt[e[i][j]] == -1) {
- mt[e[i][j]] = i;
- tm[i] = e[i][j];
- break;
- }
- }
- }*/
- int found = -1;
- for (int run = 1; run;) {
- run = 0;
- tmr++;
- for (int i = 0; i < n; i++) if (tm[i] == -1 && dfs(i)) run = 1;
- }
- for (int i = 0; i < n; i++) if (tm[i] == -1) found = i;
- printf("Case #%d: ", ++test);
- if (found == -1) {
- printf("There is no excessive subset of managers.\n");
- } else {
- tmr++;
- dfs(found);
- vector<int> v;
- for (int i = 0; i < n; i++) if (when[i] == tmr) v.push_back(i + 1);
- printf("Manager");
- if (v.size() != 1) printf("s");
- printf(" ");
- for (int i = 0; i + 2 < (int)v.size(); i++) printf("%d, ", v[i]);
- for (int i = max(0, (int)v.size() - 2); i + 1 < (int)v.size(); i++) {
- printf("%d and ", v[i]);
- }
- printf("%d form", v[(int)v.size() - 1]);
- if (v.size() == 1) printf("s");
- printf(" an excessive subset.\n");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement