笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「无聊的上下界最小流」 UVA1440 Inspection

posted on 2020-05-30 18:44:27 | under 题解 |

求解无权 DAG 的最小路径覆盖。特别的,路径可以重复走。

很神奇一道题。神奇在我在 check 自己的 Sol 的时候发现了这么一回事:

对于图中的每个点 $i$,设 $d_i$ 为( $i$ 的入度 - $i$ 的出度)的值,按照 $d_i$将图中的点分类:

$d_i<0$ 的称为“入少出多”的点,$d_i>0$ 的称为“出少入多”的点,$d_i=0$ 的称为“入出相等”的点。则有:

定理:有向无环图中最小边路径覆盖的值等于图中所有“入少出多”的点的 $d_i$ 绝对值之和。

这还是比较显然的,注意到这个定理是在陈述「边覆盖」就不难理解了。 然后借此先说 Sol 1:

Sol 1

考虑本题和不能重复走的最小路径覆盖有什么区别,那必然是存在一些路径可以重复经过。我断言,这样的路径必然满足起点 $d_i>0$,终点的 $d_i<0$ ,否则没有必要重复经过。考虑某条这样的路径 $(s:t)$ 每被重复经过一次,就必然是为了将 $t$ 之后的某条路经和 $s$ 之前的某条路径拼插起来,这样原来需要 $2$ 次现在就只需要 $1$ 次。

于是考虑直接对着这个跑一次最大流即可,各个地方的流量都是 $1$ ,拿定理中的答案减去这个最大流就好了。

Sol 2

…发现这题就是一个带下界的最小流。于是就跑一个带下界的最小流即可。

具体的,就是发现每条边都必须要至少跑一次。那么就是一条 $\rm lower=1,upper=1$ 的边。随便连一下源点汇点跑一个最小流就好了。

输出方案。考虑输出方案就只需要按照流过的边 dfs 即可。不难知道这样是对的。

我写的是 Sol2 里的代码,因为最近正在复习上下界。

ISAP即是真理,Dinic需要清除

不过感觉显然 Sol2 无聊了好几倍啊?

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>

const int N = 200010 ;

const int M = 300010 ;

const int Inf = 1000000007 ;

using namespace std ;

template <typename T>
void debug(T x, char c = '\n'){ cerr << x << c ; }

template <typename T>
void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
    for (int i = minn ; i <= maxn ; ++ i) debug(tp[i], v) ;  cerr << c ;
}

typedef long long ll ;

void chkmin(int &x, int t){ x = x < t ? x : t ; }

void chkmin(ll &x, ll t){ x = x < t ? x : t ; }

namespace ISAP{
    #define to(k) e[k].to
    #define cap(k) e[k].cap
    #define cost(k) e[k].cost
    #define from(k) e[k].from
    #define flow(k) e[k].flow
    struct edge{
        int from ;
        ll flow ;
        ll cap ;
        int to ;
        edge (int a = 0, int b = 0, ll c = 0){
            from = a, to = b, cap = c, flow = 0 ;
        }
    } e[M] ;
    int n ;
    ll ans ;
    int cnt ;
    int S, T ;
    int h, t ;
    int que[N] ;
    int pre[N] ;
    int hgt[N] ;
    int cur[N] ;
    int gap[N] ;
    vector <int> E[N] ;
    void add(int x, int y, ll c){
        e[++ cnt] = edge(x, y, c) ; E[x].push_back(cnt) ;
        e[++ cnt] = edge(y, x, 0) ; E[y].push_back(cnt) ;
    }
    void reset(int x, int y, int z){
        memset(cur, 0, sizeof(cur)) ;
        memset(hgt, 0, sizeof(hgt)) ;
        memset(gap, 0, sizeof(gap)) ;
        S = x, T = y, n = z ; cnt = -1 ;
        for (int i = 1 ; i <= n ; ++ i) E[i].clear() ;
    }
    void prebfs(){
        que[h = t = 1] = T ;
        while (h <= t){
            int x = que[h ++] ;
            for (auto k : E[x])
                if (!hgt[to(k)] && to(k) != T)
                    hgt[que[++ t] = to(k)] = hgt[x] + 1 ;
        }
        for (int i = 1 ; i <= n ; ++ i) gap[hgt[i]] ++ ;
    }
    void Aug(){
        int x = T ;
        ll z = 1ll << 60 ;
        while (x != S){
            chkmin(z, cap(pre[x]) - flow(pre[x])) ;
            x = from(pre[x]) ;
        }
        ans += z ; x = T ;
        while (x != S){
            flow(pre[x]) += z ;
            flow(pre[x] ^ 1) -= z ;
            x = from(pre[x]) ;
        }
    }
    bool Advance(int x, int &y){
        bool ret = 0 ;
        for (int d = cur[x] ; d < E[x].size() ; ++ d){
            int k = E[x][d] ;
            if (flow(k) >= cap(k)) continue ;
            if (hgt[x] != hgt[to(k)] + 1) continue ;
            cur[x] = d ; ret = 1 ;
            pre[y = to(k)] = k ; break ;
        }
        return ret ;
    }
    void isap(){
        int x = S ;
        for (int i = 1 ; i <= n ; ++ i)
            hgt[i] = gap[i] = 0 ; prebfs() ;
        while (hgt[S] < n){
//            cout << x << '\n' ;
            if (x == T)
                Aug(), x = S ;
            if (!Advance(x, x)){
                int minh = n - 1 ;
                for (auto k : E[x])
                    if (flow(k) < cap(k))
                        chkmin(minh, hgt[to(k)]) ;
                if (!-- gap[hgt[x]]) return ;
                gap[hgt[x] = minh + 1] ++ ; cur[x] = 0 ;
                if (x != S) x = from(pre[x]) ;
            }
        }
    }
}
namespace YES_Lower_Upper_Minimum{
    using namespace :: ISAP ;
    void add_e(int x, int y, int c1, int c2){
//        cout << x << " " << y << " " << c1 << " " << c2 << '\n' ;
        add(S, y, c1) ; add(x, T, c1) ; add(x, y, c2 - c1) ;
    }
    void solve(int s, int t){
        isap() ; //puts("%%%%");//debug(ans) ;
        add_e(t, s, 0, Inf), ans = 0 ;
        isap() ; cout << ans << "\n" ;
    }
    void do_back(int o){
        for (int i = 0 ; i <= cnt ; ++ i)
            if (from(i) <= o && to(i) <= o && cap(i) > 0) ++ flow(i) ;
    }
    bool _space ;
    void dfs(int x, int o){
        if (!_space)
             putchar(' ') ;
        else _space = 0 ;
        cout << x ;
        for (auto k : E[x])
            if (to(k) <= o && flow(k) > 0){
                flow(k) --, dfs(to(k), o) ; break ;
            }
    }
    void do_(int s, int o){
        while (ans){
            for (auto k : E[s]){
                if (to(k) <= o){
                    if (flow(k)){
                        _space = 1 ;
                        -- flow(k), -- ans ;
                        dfs(to(k), o), puts("") ;
                    }
                }
            }
        }
    }
}

int n, m, s, t ;

using ISAP :: reset ;
using YES_Lower_Upper_Minimum :: do_ ;
using YES_Lower_Upper_Minimum :: dfs ;
using YES_Lower_Upper_Minimum :: add_e ;
using YES_Lower_Upper_Minimum :: solve ;
using YES_Lower_Upper_Minimum :: do_back ;

int main(){
    int x, y, i ;
    while (scanf("%d", &n) == 1){
        s = n + 1, t = n + 2 ;
        reset(t + 1, t + 2, t + 2) ;
        for (x = 1 ; x <= n ; ++ x){
            scanf("%d", &i) ;
            while (i --){
                scanf("%d", &y) ;
                add_e(x, y, 1, Inf) ;
            }
            add_e(s, x, 0, Inf) ;
            add_e(x, t, 0, Inf) ;
        }
        solve(s, t) ;
        do_back(n) ;
        do_(s, n) ;

    }
    return 0 ;
}