【解析】欧拉筛法,奇偶分析。建二分图,网络流
[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]