ABC 214 G,H 題解

ABC 214 G,H 題解

考慮建一張圖。

途中\(p_i,q_i\)之間有一條邊。

則問題轉化成，在每條邊上寫上兩兩不同的數字，使得每一條邊寫的數字和兩端的數字不同。

考慮容斥。

欽定一些邊，然後給邊定向，使得每一個點的出度\(\leq 1\)。

可以發現構成的連通塊是個環，直接破環為鍊dp。

然後對于所有環做一次卷積就是答案。

時間複雜度\(O(N^2\log N)\)。

code:

很顯然是費用流。

但是spfa會被卡。

需要用dijkstra費用流。

方法：令\(h[i]\)表示目前從\(s\)到\(i\)的最短路減去上一次增廣前\(s\)到\(i\)的最短路。

然後考慮對\(h\)跑對短路。

邊權\(u\rightarrow v,w\)變成\(w+dis[u]-dis[v]\)。可以發現這個總是\(\geq 0\)。

然後就做完了。