ARC092 C. 2D Plane 2N Points
Difficulty:1268
問題
$ N個の赤い点と$ N個の青い点がある。それぞれ座標が定まっている。$ x座標と$ y座標が両方青い点より小さいような赤い点と青い点をペアにすることができるときペアは最大何ペアできるか。
解法
最大何ペアできるか、という問題は二部マッチングそのものなので、フローで解くことができる。貪欲にとる方法もあるらしいが、今回は$ O(N^2)かけて各ペアが作ることができるかを計算できるのでフローでよい。ACLに$ {mf\_graph}があるのでそれを使う。
実装
code:cpp
bool solve(){
LL(n);
vector<ll>a(n),b(n),c(n),d(n);
mf_graph<ll>g(2*n+2);
ll S = 0,T = 2*n+1;
rep(i,n){
rep(j,n){
g.add_edge(i+1,n+j+1,1);
}
}
}
rep(i,n){
g.add_edge(S,i+1,1);
g.add_edge(n+i+1,T,1);
}
O(g.flow(S,T));
return false;
}