Advertisement
Guest User

Untitled

a guest
Oct 20th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. // This file is a "Hello, world!" in C++ language by GCC for wandbox.
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long int uli;
  5.  
  6. /*
  7. Dinic is a struct with two methods:
  8. 1. AddEdge(u,v,c): adds an edge from u to v with capacity c
  9. 2. MaxFlow(s,t): calculates the Maximum Flow with source s and sink t
  10. */
  11.  
  12. class Dinic{
  13. private:
  14.     pair<int,pair<int,int>> *Arr;
  15. public:
  16.     Dinic(int n){
  17.         Arr = new pair<int,pair<int,int>>[n];
  18.     }
  19.    
  20.     void AddEdge(int u, int v, int c){
  21.         pair<int,pair<int,int>> elem;
  22.         elem.first = u;
  23.         elem.second.first =  v;
  24.         elem.second.second = c;
  25.         Arr.pushback(elem);
  26.     }
  27. };
  28.  
  29. int a[55],b[55];
  30. int main(){
  31.   int n;
  32.   scanf("%d",&n);
  33.   for(int i=0;i<n;i++){
  34.     scanf("%d %d",a+i,b+i);
  35.     --a[i],--b[i];
  36.   }
  37.   int s=n+n;
  38.   int t=s+1;
  39.   int ans=0;
  40.   for(int i=0;i<n;i++){
  41.     //number of people that want to kill i
  42.     int cnt=0;
  43.     for(int j=0;j<n;j++)
  44.       if(a[j]==i || b[j]==i)
  45.         cnt++;
  46.     //if cnt<=1 the werewolf can at least tie
  47.     if(cnt<=1){
  48.       ans++;
  49.       continue;
  50.     }
  51.     Dinic din(n+n+2);
  52.     for(int j=0;j<n;j++)if(j!=i){
  53.       din.AddEdge(s,j,1);
  54.       int cap=cnt-1;
  55.       if(j==a[i] || j==b[i])cap--;
  56.       din.AddEdge(j +n,t,cap);
  57.  
  58.       if(a[j]!=i && b[j]!=i){
  59.         din.AddEdge(j,a[j] +n,1);
  60.         din.AddEdge(j,b[j] +n,1);
  61.       }
  62.     }
  63.     uli flw=din.MaxFlow(s,t);
  64.     if(flw<n-1-cnt)ans++;
  65.   }
  66.   printf("%d\n",ans);
  67.   return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement