P2770 说一点关于此题的小细节

皎月半洒花

2020-03-17 09:48:24

Solution

说一点实现上的小细节吧。主要内容是「跟其他题解不一样的东西」。 发现大家在做这个题的时候,都是特判的「是否存在一条直接连通 $1$ 和 $n$」 的路径,然后直接输出。首先这么做,较为麻烦(虽然也就只多了一两二三行),其次正确性有待考究。 这个地方就需要思考,为什么大家的实现需要特判这个细节?原因是假设只有 $1\leftrightarrow n$ 这一条边,那么这条路需要走两次。但是连边 $(u,v)$ 的时候大家都是写的 `add(u',v,1,0)`,导致只能走一次。个人认为,由于这是个基础题,所以每个细节都需要写的十分合理,但这个地方显然就不合理。 网络流题讲究对着限制找`flow`,对着代价找`cost`。这个题目里显然只限制了一个点至多走一次,但是没限制一条边至多走一次——虽然本质上,没啥很大区别,因为点至多一次决定了边至多一次——但是这从某种程度上决定了对这个题建模的理解程度。所以我认为,为了更好地实现「网络流24题」的网络流教学任务,应该在连边 $(u,v)$ 时如是写: ```cpp add(u',v,Inf,0) ``` 这样有两个好处: 1、只需要特判无解,根本不需要那些无聊的判来判去判流量多少,影响代码的美观和简练。 2、体现了这个题建模的本质意义。因为已经有拆点保证了题目中的要求的限制,如果再硬生生加上一个「边也至多走一次」,就是在无中生有、暗度陈仓(雾)。而精准的建模是网络流学习阶段所必须掌握的东西。 ```cpp int main(){ cnt = -1 ; cin >> _n >> _m ; x = _n * 2 ; y = 1 + _n ; _s = 0 ; _t = _n + _n + 1 ; memset(head, -1, sizeof(head)) ; add(_s, 1, 2, 0) ; add(x, _t, 2, 0) ; add(1, y, 2, -1) ; add(_n, x, 2, -1) ; for (int i = 1 ; i <= _n ; ++ i) cin >> s, rt[t[s] = i] = s ; for (int i = 1 ; i <= _n ; ++ i) add(i, i + _n, 1, -1) ; for (int i = 1 ; i <= _m ; ++ i){ cin >> s >> ss ; int p = t[s] ; int q = t[ss] ; if (p > q) swap(p, q) ; //cout << p << " " << q << endl ; add(p + _n, q, I, 0) ; } buc[1] = 1 ; n = _t + 1 ; ek() ; if (!ret) return puts("No Solution!"), 0 ; cout << -res - 2 << endl ; dfs(1, l) ; cout << rt[1] << endl ; for (int i = 0 ; i < l ; ++ i) cout << rt[ans[i]] << '\n' ; l = 0 ; for (int i = 0 ; i <= cnt ; ++ i) if (ct(i) == -1 && !fw(i) && !buc[fr(i)]) ans[++ l] = fr(i) ; sort(ans + 1, ans + l + 1, comp) ; for (int i = 1 ; i <= l ; ++ i) cout << rt[ans[i]] << '\n' ; return cout << rt[1] << endl, 0 ; } ``` btw,其实只需要dfs一遍即可。由于访问过程一定是单调的,所以将走完一遍后那些没走过的节点排序输出即可。