Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // This file is a "Hello, world!" in C++ language by GCC for wandbox.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int uli;
- /*
- Dinic is a struct with two methods:
- 1. AddEdge(u,v,c): adds an edge from u to v with capacity c
- 2. MaxFlow(s,t): calculates the Maximum Flow with source s and sink t
- */
- class Dinic{
- private:
- pair<int,pair<int,int>> *Arr;
- public:
- Dinic(int n){
- Arr = new pair<int,pair<int,int>>[n];
- }
- void AddEdge(int u, int v, int c){
- pair<int,pair<int,int>> elem;
- elem.first = u;
- elem.second.first = v;
- elem.second.second = c;
- Arr.pushback(elem);
- }
- };
- int a[55],b[55];
- int main(){
- int n;
- scanf("%d",&n);
- for(int i=0;i<n;i++){
- scanf("%d %d",a+i,b+i);
- --a[i],--b[i];
- }
- int s=n+n;
- int t=s+1;
- int ans=0;
- for(int i=0;i<n;i++){
- //number of people that want to kill i
- int cnt=0;
- for(int j=0;j<n;j++)
- if(a[j]==i || b[j]==i)
- cnt++;
- //if cnt<=1 the werewolf can at least tie
- if(cnt<=1){
- ans++;
- continue;
- }
- Dinic din(n+n+2);
- for(int j=0;j<n;j++)if(j!=i){
- din.AddEdge(s,j,1);
- int cap=cnt-1;
- if(j==a[i] || j==b[i])cap--;
- din.AddEdge(j +n,t,cap);
- if(a[j]!=i && b[j]!=i){
- din.AddEdge(j,a[j] +n,1);
- din.AddEdge(j,b[j] +n,1);
- }
- }
- uli flw=din.MaxFlow(s,t);
- if(flw<n-1-cnt)ans++;
- }
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement