POJ 1637 Sightseeing tour 混合图欧拉回路 网络流

先考虑联通性,不连通则无解。

再给所有双向边钦点一个方向,和单向边一样记录入度出度。

然后我们考虑,对于一个点,把一条双向边的方向改变,入度-出度的奇偶性是不变的,这样子我们看一下,所有点的入度-出度,如果为奇数,则无解。

然后我们对于每个点,如果其出度大于入度,则从s到i连一条流量为(oud[i] – ind[i]) / 2的边,代表这个点需要反向的边的数量。如果其入度大于出度,从则i到t连一条流量为(ind[i] – oud[i]) / 2的边,代表这个点需要反向边的数量。对于每一个双向边,我们都从以最初钦点的方向连一条流量为1的边。

然后我们跑最大流,如果从s出来的所有边都满流,则证明存在欧拉回路。我们将有1流量流过的边的方向取反则得到方案。

如果混合图要求欧拉道路,则有且仅有2个点入度-出度的为奇数,在这两点间连一条边,判断是否存在欧拉回路。

发表评论