Quiz
AC
解説
- ワーシャルフロイドで最短距離を求め、アルファベットの条件を満たす頂点間を辺でつないだ新たなグラフGを考える
- Gはアルファベットの条件から2部グラフ
- 最小点被覆の位置に罠を置けばいい
その他
- コンテスト中はvertex coverを全く考えなかったので葉の隣に罠を置いたりした
- それだと輪っかの時に置けないので、輪っか状態なら適当に置いたりもした
- そういうその場しのぎ的な解法では全ACは取れず
最大流ライブラリ
code
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll N,M,K;
cin>>N>>M>>K;
vector<char> C(N);
rep(i,N)cin>>C[i];
VI A(M);
VI B(M);
rep(i,M){
cin>>A[i]>>B[i];
A[i]--;
B[i]--;
}
WarshallFloyd wa(N);
rep(i,M){
wa.register_edge2(A[i],B[i],1);
}
wa.calc();
MaxFlow flow(N+2);
ll start = N;
ll end = N+1;
rep(i,N){
FOR(j,i+1,N){
if(wa.distance(i,j)<=K and next(C[i],C[j])){
ll v = C[i]-'a';
if(v%2==0){
flow.add_edge(i, j, 1);
}else{
flow.add_edge(j, i, 1);
}
}
}
}
rep(i,N){
ll v = C[i]-'a';
if(v%2==0){
flow.add_edge(start, i, 1);
}else{
flow.add_edge(i, end, 1);
}
}
ll max_flow = flow.calc(start, end);
p(max_flow);
return 0;
}