2020年3月18日水曜日

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

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


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