//時間計測用 //構築未実装 #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define INF 1000000000000000000 ostream& operator<<(ostream& os,queue a){ while(!a.empty()){ ll t=a.front(); a.pop(); os<y)return y; return x; } struct edge3{ ll to,cap,rev; }; ostream& operator<<(ostream& os,edge3& a){ return os<& a){ for(edge3 i:a){ os<* G; ll* level; ll* iter; */ vector G[200010]; ll level[200010]; ll iter[200010]; //Dinic(){} /* Dinic(ll max_v){ MAX_V = max_v; G=new vector[MAX_V]; level=new ll[MAX_V]; iter=new ll[MAX_V]; } */ void add_edge(ll from,ll to,ll cap){ G[from].push_back((edge3){to,cap,(ll)G[to].size()}); G[to].push_back((edge3){from,0,(ll)G[from].size()-1}); } void bfs(ll s){ memset(level,-1,sizeof(level)); queue que; level[s]=0; que.push(s); while(!que.empty()){ //cout<0 && level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } } } ll dfs(ll v,ll t,ll f){ if(v==t)return f; //cout<<"&i:"<0 && level[v]0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } ll max_flow(ll s,ll t){ ll flow=0; for(;;){ bfs(s); //cout<<"bfs end\n"; if(level[t]<0)return flow; //cout<0){ //cout<>N; //Dinic F(200002); //Dinic F; //cout<<"INF:"<>A>>B; A--;B--; /* F.add_edge(200000,i,1); F.add_edge(i,100000+A,1); if(A!=B)F.add_edge(i,100000+B,1); F.add_edge(100000+i,200001,1); */ add_edge(200000,i,1); add_edge(i,100000+A,1); if(A!=B)add_edge(i,100000+B,1); add_edge(100000+i,200001,1); } //cerr<<"edge added\n"; //ll cnt=F.max_flow(200000,200001); ll cnt=max_flow(200000,200001); //cout<