fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class MaxFlow {
  6.     int V;
  7.     vector<vector<int>> capacity;
  8.     vector<vector<int>> adj;
  9.  
  10. public:
  11.     MaxFlow(int V) : V(V), capacity(V, vector<int>(V, 0)), adj(V) {}
  12.  
  13.     void add_edge(int u, int v, int cap) {
  14.         capacity[u][v] = cap;
  15.         adj[u].push_back(v);
  16.         adj[v].push_back(u); // Reverse edge for residual graph
  17.     }
  18.  
  19.     int bfs(int s, int t, vector<int>& parent) {
  20.         fill(parent.begin(), parent.end(), -1);
  21.         parent[s] = -2;
  22.         queue<pair<int, int>> q;
  23.         q.push({s, INT_MAX});
  24.  
  25.         while (!q.empty()) {
  26.             int cur = q.front().first;
  27.             int flow = q.front().second;
  28.             q.pop();
  29.  
  30.             for (int next : adj[cur]) {
  31.                 if (parent[next] == -1 && capacity[cur][next] > 0) {
  32.                     parent[next] = cur;
  33.                     int new_flow = min(flow, capacity[cur][next]);
  34.                     if (next == t)
  35.                         return new_flow;
  36.                     q.push({next, new_flow});
  37.                 }
  38.             }
  39.         }
  40.         return 0;
  41.     }
  42.  
  43.     int maxflow(int s, int t) {
  44.         int flow = 0;
  45.         vector<int> parent(V);
  46.         int new_flow;
  47.  
  48.         while ((new_flow = bfs(s, t, parent))) {
  49.             flow += new_flow;
  50.             int cur = t;
  51.             while (cur != s) {
  52.                 int prev = parent[cur];
  53.                 capacity[prev][cur] -= new_flow;
  54.                 capacity[cur][prev] += new_flow;
  55.                 cur = prev;
  56.             }
  57.         }
  58.         return flow;
  59.     }
  60. };
  61.  
  62. bool canForceLose(vector<pair<int, int>> &options, int which){
  63. 	int n = options.size();
  64. 	int votes = 0;
  65.  
  66.     int source = 2 * n, sink = 2 * n + 1;
  67.     MaxFlow mf(2 * n + 2);
  68.  
  69.     auto strategic = options[which];//this will be the last decision and is strategic
  70.     for (int i = 0; i < n; i++) {
  71.     	if(i==which) continue;
  72. 		auto pp = options[i];
  73. 		if(pp.first == which || pp.second == which){
  74. 			++votes;
  75. 		}else{
  76.         	mf.add_edge(source, i, 1);
  77. 	        mf.add_edge(i, pp.first + n, 1);
  78. 	        mf.add_edge(i, pp.second + n, 1);
  79. 		}
  80. 	}
  81.     for (int i = 0; i < n; i++) {
  82.     	//you can vote at most (votes-1) times for non-strategic candidates
  83.     	//but you can vote at most (votes-2) times for strategic candidates
  84.     	//else that last strategic vote can overturn the election with a tie
  85.     	int maxAllowedVotes = i==strategic.first || i == strategic.second ? votes-2 : votes-1;
  86.         if(maxAllowedVotes > 0) mf.add_edge(i + n, sink, maxAllowedVotes);
  87.     }
  88.     //could I assign all votes to a candidate while complying with the constraints?
  89.     return mf.maxflow(source, sink) + votes + 1 == n;//+1 because of the last strategic vote
  90. }
  91.  
  92.  
  93. int main(int argc, char* argv[]) {
  94.     vector<pair<int, int>> edges;
  95.     int n = 0;
  96.     cin>>n;
  97.     for(int i = 0;i<n;++i){
  98.     	int a, b;
  99.     	cin >> a >> b; --a;--b;
  100.         edges.emplace_back(a, b);
  101.     }
  102.  
  103.     int ans = 0;
  104.     for(int i = 0;i<n;++i){
  105.     	ans+=!canForceLose(edges, i);
  106.     }
  107.     cout<<ans<<endl;
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
4
3 4
1 4
4 1
3 1
stdout
copy 
2
https://ideone.com/bPw6Kk
language:
C++14 (gcc 8.3)
created:
4 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!