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

· · 题解

说一点实现上的小细节吧。主要内容是「跟其他题解不一样的东西」。

发现大家在做这个题的时候，都是特判的「是否存在一条直接连通 1 和 n」 的路径，然后直接输出。首先这么做，较为麻烦(虽然也就只多了一两二三行)，其次正确性有待考究。

这个地方就需要思考，为什么大家的实现需要特判这个细节？原因是假设只有 1\leftrightarrow n 这一条边，那么这条路需要走两次。但是连边 (u,v) 的时候大家都是写的 add(u',v,1,0)，导致只能走一次。个人认为，由于这是个基础题，所以每个细节都需要写的十分合理，但这个地方显然就不合理。

网络流题讲究对着限制找flow，对着代价找cost。这个题目里显然只限制了一个点至多走一次，但是没限制一条边至多走一次——虽然本质上，没啥很大区别，因为点至多一次决定了边至多一次——但是这从某种程度上决定了对这个题建模的理解程度。所以我认为，为了更好地实现「网络流24题」的网络流教学任务，应该在连边 (u,v) 时如是写：

add(u',v,Inf,0)

这样有两个好处：

1、只需要特判无解，根本不需要那些无聊的判来判去判流量多少，影响代码的美观和简练。

2、体现了这个题建模的本质意义。因为已经有拆点保证了题目中的要求的限制，如果再硬生生加上一个「边也至多走一次」，就是在无中生有、暗度陈仓(雾)。而精准的建模是网络流学习阶段所必须掌握的东西。

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一遍即可。由于访问过程一定是单调的，所以将走完一遍后那些没走过的节点排序输出即可。