2020年3月18日水曜日

CODE FESTIVAL 2014 予選B C - 錬金術師

最大流で解ける。source, sink, S1, S2と26種類のアルファベットに対応する頂点の計30頂点を用意する。source→S1, source→S2に容量NNの辺を張り、S1から各アルファベットccに向かってS1に含まれているccの総数に等しい容量の辺を張り、S2についても同様にする。最後に、各アルファベットccからsinkに向かってS3S3に含まれているccの総数に等しい容量の辺を張る。このネットワークに容量2N2Nのフローが流せればYESということになる。


第一感がフローなのは成長なのか退化なのか。