# 笨蛋花的小窝qwq

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

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

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

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

### Sol 2

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

ISAP即是真理，Dinic需要清除

#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 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 ;
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' ;
}
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 :: 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) ;