天天看点

【Codeforces】512C Fox and Dinner

【解析】欧拉筛法,奇偶分析。建二分图,网络流

[Analysis]

所谓的连通块就是指满流了,因为我直接使用剩余流量求网络流。

至于怎样推断满流,我想到下面几种:

①对于初始的网络。若图的流向是一样的。那么就直接推断对于一条边k的正向边k>>1<<1是否满流。

②对于一般的,能够存流量限制。

③或者对每条边再存个tag。若tag=1,则表示初始时这条边容量限制非0,否则是0。

[Q&A]

问题1:为什么这样搜索能够出解而不错误?

回答1:这不是非常明显的嘛,因为满流了,所以除原点和汇点外的每一个节点连接且仅连接两个节点。

这样从一个节点过来。那么必定仅仅能从还有一个节点出去。

最后必定会有一个节点连接到第一个节点。这是就停止了。假如没有。那么一直找到了第n个节点就找不到了。矛盾。

特殊的,对于每一个连通集合的第一个节点,选择了随意一个相邻的节点,这也是没问题的。

[Sum]

①对于素数的问题,要想到奇偶分析。

②k!=-1。等价于~k,这里能够化简。事实上scanf("%d",&a)这个函数假设读不到不论什么东西,返回的值也是-1。

之所以能这样由于-1的二进制为最大即2^k-1,取反后为0。而其它取反都非0。

③推断满流的三种办法。

④回想了网络流算法。

[Code]