Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define sz(x) ((int)x.size ())
- const int N = 2000;
- const int inf = 1e9 + 7;
- int used[N], in[N], w[N];
- int timer = 1;
- vector<int> g[N];
- int was[N], s, t;
- struct edge {
- int fr, to, f;
- };
- vector<edge> e;
- void make (int a, int b, int c) {
- g[a].push_back(sz(e));
- e.push_back({a, b, c});
- g[b].push_back(sz(e));
- e.push_back({b, a, 0});
- }
- int go (int v, int flow = inf) {
- was[v] = timer;
- if (v == t) return flow;
- for (auto i : g[v])
- if (e[i].f && was[e[i].to] != timer) {
- int push = go (e[i].to, min (flow, e[i].f));
- if (push) {
- e[i].f -= push;
- e[i^1].f += push;
- return push;
- }
- }
- return 0;
- }
- void dfs (int v, int c, vector<vector<int>>& gr, vector<int>& A, vector<int>& B) {
- used[v] = 1 + c;
- if (!c) A.push_back(v);
- else B.push_back(v);
- for (auto x : gr[v])
- if (used[x] == 0)
- dfs (x, c ^ 1, gr, A, B);
- }
- vector<int> get (vector<int>& p, vector<int>& A, int pos, vector<vector<int>>& gr) {
- vector<int> ans(sz(A));
- for (int i = 0; i < sz(A); i++) {
- for (auto x : gr[A[i]])
- if (w[x] >= 0 && p[w[x]] == pos)
- ans[i] = 1;
- }
- return ans;
- }
- bool go (int pos, vector<int>& p, vector<int>& ans, vector<vector<int>>& gr, int n, vector<int>& S, vector<int>& A, vector<int>& B) {
- if (pos == sz(p)) {
- int ok = 0;
- vector<int> T;
- int k = sz(p);
- for (int i = 0; i < k; i++) {
- in[S[i]] = (p[i] == 0);
- if (p[i] == 2) T.push_back(S[i]);
- }
- for (int i = 0; i < k; i++) {
- if (p[i] == 0)
- for (auto x : gr[S[i]])
- ok |= in[x];
- }
- for (int i = 0; i < k; i++) {
- in[S[i]] = (p[i] == 1);
- }
- for (int i = 0; i < k; i++) {
- if (p[i] == 1)
- for (auto x : gr[S[i]])
- ok |= in[x];
- }
- if (ok) return false;
- if (ok) return false;
- auto Al = get (p, A, 0, gr);
- auto Ar = get (p, A, 1, gr);
- auto Bl = get (p, B, 0, gr);
- auto Br = get (p, B, 1, gr);
- vector<int> AlBr, ArBl;
- for (int i = 0; i < sz(A); i++) {
- if (Al[i]) AlBr.push_back(A[i]);
- if (Ar[i]) ArBl.push_back(A[i]);
- }
- for (int i = 0; i < sz(B); i++) {
- if (Br[i]) AlBr.push_back(B[i]);
- if (Bl[i]) ArBl.push_back(B[i]);
- }
- e.clear();
- s = 2 * n;
- t = s + 1;
- for (int i = 0; i <= t; i++) g[i].clear();
- for (int i = 0; i < n; i++)
- if (used[i] != -1) {
- make (i, n + i, 1);
- for (auto x : gr[i])
- if (used[x] != -1)
- make (n + i, x, 1);
- }
- for (auto x : AlBr) make (s, x, 1);
- for (auto x : ArBl) make (x + n, t, 1);
- timer++;
- int flow = 0;
- int cur;
- while (cur = go(s)) {
- flow += cur;
- timer++;
- if (flow >= sz(S) - sz(T)) break;
- }
- if (flow < sz(S) - sz(T)) {
- for (int i = 0; i < sz(e); i += 2)
- if (e[i].fr == s && !e[i].f) ans.push_back(e[i].to);
- for (auto x : T) ans.push_back(x);
- return true;
- }
- return false;
- }
- for (int i = 0; i < 3; i++) {
- p[pos] = i;
- if (go (pos + 1, p, ans, gr, n, S, A, B)) return true;
- }
- return false;
- }
- bool solve (int n, vector<vector<int>>& gr, vector<int>& s, vector<int>& ans) {
- memset (w, -1, sizeof(w[0]) * n);
- memset (used, 0, sizeof(used[0]) * n);
- memset (in, 0, sizeof(in[0]) * n);
- vector<int> A, B;
- int k = sz(s);
- vector<int> t(k);
- for (int i = 0; i < k; i++)
- used[s[i]] = -1, w[s[i]] = i;
- for (int i = 0; i < n; i++)
- if (used[i] == 0)
- dfs (i, 0, gr, A, B);
- if (go (0, t, ans, gr, n, s, A, B)) {
- return true;
- }
- return false;
- }
- bool tunec (int n, vector<vector<int>>& g, int k, vector<int>& ans) {
- if (n - 1 <= k) {
- for (int i = 0; i < k; i++)
- ans.push_back(i);
- return true;
- }
- vector<int> s(k + 1);
- for (int i = 0; i <= k; i++) s[i] = i;
- vector<vector<int>> gr(n);
- for (int i = 0; i < k; i++)
- for (auto x : g[i])
- if (x < i) {
- gr[i].push_back(x);
- gr[x].push_back(i);
- }
- for (int i = k; i < n; i++) {
- for (auto x : g[i])
- if (x < i) {
- gr[i].push_back(x);
- gr[x].push_back(i);
- }
- if (sz(s) <= k) {
- if (i != n - 1) s.push_back(i + 1);
- continue;
- }
- vector<int> x;
- auto ok = solve (i + 1, gr, s, x);
- if (!ok) break;
- if (i != n - 1) x.push_back(i + 1);
- s = x;
- }
- if (sz(s) <= k) {
- ans = s;
- return true;
- }
- return false;
- }
- int main() {
- int n, m, k;
- cin >> n >> m >> k;
- vector<vector<int>> gr(n);
- for (int i = 0; i < m; i++) {
- int x, y;
- cin >> x >> y;
- x--; y--;
- gr[x].push_back(y);
- gr[y].push_back(x);
- }
- vector<int> s(k), ans;
- for (int i = 0; i < k; i++) cin >> s[i], s[i]--;
- if (solve (n, gr, s, ans)) {
- for (auto x : ans) cout << x + 1 << " ";
- }
- else cout << "No solution";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement