AT_joisc2016_i 電報 题解

考虑什么时候图合法。很显然，当且仅当图有且仅有一个环构成时图合法。更确切的说，一个图合法当且仅当：

• 将所有的单向边扩展为双向边后图连通。
• 图中任意一个点 $u$ 的入度为 $1$。

因此首先特判掉图已经合法的情况，剩下的情况图是一个基环森林，需要将森林中的每一个基环树都经过若干次操作使得该树中所有结点都只保留一条入边。有一个显然的贪心是说对于每一个点记录其入边所有边需要修改的权值，然后对于每一个入度 $>1$ 的点保留边权最大的入边，其余的入边删去。但是这个贪心其实是错的，此时图有可能成为若干个不连通的环。因此考虑在贪心中叠加一个条件：对于每一个环，至少需要更新一条环上的边，使其连向另一个环。

根据上述贪心策略模拟即可。时间复杂度为线性。