题目链接

题意:给出 n 个点 m 条边的无向图,定向得到有向无环图,使得最长路最短。


Dliworth 定理 的对偶定理:DAG 最长链=最小反链覆盖

显然一个点集如果内部没有点直接相连,一定可以定向使得没有点间接相连

\(g_i\) 表示点集\(i\) 内部是否有点直接相连,\(f_i\) 表示点集\(i\) 的最小反链覆盖,转移的时候枚举子集即可。

话说好久没写博客了... 一直在闷声水模拟赛...

 


一个非常弱的准退役OIER