Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <bitset>
- #include <algorithm>
- #include <functional>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- using namespace std;
- const int oo = 1 << 28;
- int n, m = 0;
- int c[1005][1005], f[1005][1005], d[1005], r[1005], color[1005], q[1005], p[1005];
- bool b[1005];
- int start, finish;
- string name[1005];
- bool ok(int i, int j){
- if (d[i] == -1 || d[j] == -1)
- return true;
- if (abs(d[i]-d[j]) == 1)
- return true;
- return false;
- };
- void dfs(int v, int g){
- b[v] = true;
- color[v] = g;
- for (int i = 1; i <= n; i++)
- if (!b[i] && c[v][i] == 1)
- dfs(i, g ^ 1);
- };
- int main() {
- freopen("in.in", "rt", stdin);
- cin >> n;
- for (int i = 0; i < n; i++) {
- string s1, s2;
- int x, cur;
- cin >> s1 >> s2 >> x;
- m++;
- cur = m;
- name[m] = s1;
- if (s2 == "anything") d[cur] = -1; else
- if (s2 == "statements") d[cur] = 0; else d[cur] = 1;
- r[cur] = x;
- }
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (abs(r[i]-r[j]) == 2 && ok(i, j))
- c[i][j] = c[j][i] = 1;
- start = 0, finish = n + 1;
- for (int i = 1; i <= n; i++)
- if (!b[i]) dfs(i, 0);
- for (int i = 1; i <= n; i++)
- if (color[i]) c[start][i] = c[i][start] = 1;
- else c[i][finish] = c[finish][i] = 1;
- while (true){
- for (int i = start; i <= finish; i++)
- q[i] = -1, p[i] = -1;
- int h = 0, t = 1;
- q[0] = start, p[start] = start;
- while (h < t) {
- int cur = q[h++];
- for (int i = 1; i <= finish; i++)
- if (p[i] == -1 && c[cur][i]-f[cur][i] > 0){
- q[t++] = i;
- p[i] = cur;
- }
- }
- if (p[finish] == -1) break;
- int cf = oo, cur = finish;
- while (cur != p[cur]){
- int prev = p[cur];
- cf = min(cf, c[prev][cur] - f[prev][cur]);
- cur = prev;
- }
- cur = finish;
- while (cur != p[cur]){
- int prev = p[cur];
- f[prev][cur] += cf, f[cur][prev] -= cf;
- cur = prev;
- }
- }
- int ans = 0;
- for (int i = 1; i <= n; i++)
- ans += f[start][i];
- printf("%d\n", ans);
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (f[i][j] == 1) {
- if (d[i] == 0 || d[j] == 1) cout << name[i] << " " << name[j]; else
- cout << name[j] << " " << name[i];
- puts("");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment