fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. constexpr int maxn = 2 * 50 + 5;
  6. constexpr int inf = 1e6;
  7. vector<int> adj[maxn];
  8. int mat[maxn][maxn];
  9. int a[maxn], b[maxn];
  10.  
  11. inline void Clean() {
  12.   for (int i = 0; i < maxn; ++i) {
  13.     adj[i].clear();
  14.     for (int j = 0; j < maxn; ++j) {
  15.       mat[i][j] = 0;
  16.     }
  17.   }
  18. }
  19.  
  20. inline void AddEdge(int u, int v, int c) {
  21.   adj[u].push_back(v);
  22.   adj[v].push_back(u);
  23.   mat[u][v] = c;
  24.   mat[v][u] = 0;
  25. }
  26.  
  27. bool Bfs(int s, int t, vector<int>& bfr) {
  28.   queue<int> q;
  29.   q.push(s);
  30.   fill(bfr.begin(), bfr.end(), -1);
  31.  
  32.   while (!q.empty()) {
  33.     int u = q.front();
  34.     q.pop();
  35.  
  36.     if (u == t) {
  37.       return true;
  38.     }
  39.     for (int v : adj[u]) {
  40.       if (bfr[v] == -1 && mat[u][v] > 0) {
  41.         q.push(v);
  42.         bfr[v] = u;
  43.       }
  44.     }
  45.   }
  46.   return false;
  47. }
  48.  
  49. int MaxFlow(int s, int t) {
  50.   int ans = 0;
  51.   vector<int> bfr(maxn);
  52.   while (Bfs(s, t, bfr)) {
  53.     int cur_flow = inf, cur_node = t;
  54.     int cnt = 0;
  55.     while (cur_node != s) {
  56.       cur_flow = min(cur_flow, mat[bfr[cur_node]][cur_node]);
  57.       cur_node = bfr[cur_node];
  58.     }
  59.     cur_node = t;
  60.     while (cur_node != s) {
  61.       mat[bfr[cur_node]][cur_node] -= cur_flow;
  62.       mat[cur_node][bfr[cur_node]] += cur_flow;
  63.       cur_node = bfr[cur_node];
  64.     }
  65.     ans += cur_flow;
  66.   }
  67.   return ans;
  68. }
  69.  
  70. int main() {
  71.   ios_base::sync_with_stdio(0);
  72.   cin.tie(0);
  73.  
  74.   int n, cnt, ans = 0;
  75.   cin >> n;
  76.   for (int i = 0; i < n; ++i) {
  77.     cin >> a[i] >> b[i];
  78.     --a[i];
  79.     --b[i];
  80.   }
  81.   int s = 2 * n, t = s + 1;
  82.   for (int i = 0; i < n; ++i) {
  83.     cnt = 0;
  84.     Clean();
  85.     for (int j = 0; j < n; ++j) {
  86.       if (i == j) {
  87.         continue;
  88.       }
  89.       if (a[j] == i || b[j] == i) {
  90.         ++cnt;
  91.       }
  92.     }
  93.     if (cnt <= 1) {
  94.     	++ans;
  95.     	continue;
  96.     }
  97.     // cout << "n: " << n << ", cnt: " << cnt << '\n';
  98.     for (int j = 0; j < n; ++j) {
  99.       if (i == j) {
  100.         continue;
  101.       }
  102.       AddEdge(s, j, 1);
  103.       if (a[j] != i && b[j] != i) {
  104.         AddEdge(j, n + a[j], 1);
  105.         AddEdge(j, n + b[j], 1);
  106.       }
  107.       int wj = cnt - 1;
  108.       if (a[i] == j || b[i] == j) {
  109.         --wj;
  110.       }
  111.       AddEdge(n + j, t, wj);
  112.     }
  113.     if (MaxFlow(s, t) < (n - cnt - 1)) {
  114.       ++ans;
  115.     }
  116.   }
  117.   cout << ans << '\n';
  118.  
  119.   return 0;
  120. }
Success #stdin #stdout 0.01s 5248KB
comments (?)
stdin
copy 
4
3 4
1 4
4 1
3 1
stdout
copy 
2
https://ideone.com/dcqYB0
language:
C++14 (gcc 8.3)
created:
41 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!