头像

鹤萝芠




离线:13小时前


新鲜事 原文

鹤萝芠
2个月前
240大众分滚粗了5555 , 还好在弱省(



鹤萝芠
2个月前
#include <bits/stdc++.h> 
using namespace std ;
const int N = 220 , inf = 0x3f3f3f3f , M = 1e4 * 2 + 210 ;
int S , T , n , m , cur[N] , dep[N] , q[N] ;
int cnt = 1 , h[N] , s[N] , tot ;

struct ga {
    int low , f , to , nxt ;
}e[M << 1] ;
void add (int a , int b , int c , int d) {
    e[++cnt] = (ga) {c , d , b , h[a]} , h[a] = cnt ;
}

bool bfs () {
    int hh = 0 , tt = 0 ;
    memset (dep , -1 , sizeof dep) ;
    q[0] = S , dep[S] = 0 , cur[S] = h[S] ;
    while (hh <= tt) {
        int u = q[hh ++] ;
        for (int i = h[u] ; i ; i = e[i].nxt) {
            int tonode = e[i].to ;
            if (dep[tonode] == -1 && e[i].f) {
                dep[tonode] = dep[u] + 1 , cur[tonode] = h[tonode] ;
                if (tonode == T) return true ;
                else q[++tt] = tonode ;
            }
        }
    }
    return false ;
}

int Find (int u , int lim) {
    if (u == T ) return lim ;
    int part = 0 ;
    for (int i = cur[u] ; i && part < lim ; i = e[i].nxt) {
        cur[u] = i ;
        int tonode = e[i].to ;
        if (e[i].f && dep[tonode] == dep[u] + 1) {
            int value = Find (tonode , min (e[i].f , lim - part)) ;
            if (!value) dep[tonode] = -1 ;
            e[i].f -= value , e[i ^ 1].f += value , part += value ;
        }
    }
    return part ;

}

int dinic () {
    int part = 0 , ans = 0 ; 
    while (bfs()) while (part = Find (S , inf)) ans += part ;
    return ans ;
}

int main () {
    scanf ("%d%d" , &n , &m) ;
    S = 0 , T = n + 1 ;
    for (int i = 1 ; i <= m ; i ++) {
        int a , b , c , d ;
        scanf ("%d%d%d%d" , &a , &b , &c , &d) ;
        add (a , b , c , d - c) , add (b , a , 0 , 0) ;
        s[a] -= c , s[b] += c ; 
    }
    for (int i = 1 ; i <= n ; i ++) {
        if (s[i] >= 0) add (S , i , 0 , s[i]) , add (i , S , 0 , 0) , tot += s[i] ;
        else add (i , T , 0 , -s[i]) , add (T , i , 0 , 0) ;
    }
    if (dinic () != tot) cout << "NO" << endl ;

    else {
        cout << "YES" << endl ;
        int res = 0 ;
        for (int i = 2 ; i <= 2 * m + 1 ; i += 2) {
            cout << e[i ^ 1].f + e[i].low << endl ;

        }

    }
    return 0 ;
}



鹤萝芠
2个月前

include [HTML_REMOVED]

using namespace std ;
const int N = 5e4 + 10 , inf = 1e8 + 33 ;

int n , m , a[N] ;

struct segt {
int l , r ;
multiset [HTML_REMOVED] s ;
}t[N << 2] ;

void buildnode (int u , int l , int r) {
t[u].l = l , t[u].r = r , t[u].s.insert (inf) , t[u].s.insert (-inf) ;
for (int i = l ; i <= r ; i ++) t[u].s.insert (a[i]) ;
if (l == r) return ;
int mid = l + r >> 1 ;
buildnode (u << 1 , l , mid) , buildnode (u << 1 | 1 , mid + 1 , r) ;
}

void modify (int u , int x , int val) {
t[u].s.erase (t[u].s.find (a[x])) , t[u].s.insert (val) ;
if (t[u].l == t[u].r) return ;
int mid = t[u].l + t[u].r >> 1 ;
if (x <= mid) modify (u << 1 , x , val) ;
else modify (u << 1 | 1 , x , val) ;
}

int query (int u , int ql , int qr , int x) {
if (t[u].l >= ql && t[u].r <= qr) {
return *–t[u].s.lower_bound (x) ;
}
int mid = t[u].l + t[u].r >> 1 ;
int res = 0 ;
if (ql <= mid) res = max (res , query (u << 1 , ql , qr , x)) ;
if (qr > mid) res = max (res , query (u << 1 | 1 , ql , qr , x)) ;
return res ;
}

int main () {
scanf (“%d%d” , &n , &m) ;
for (int i = 1 ; i <= n ; i ++) scanf (“%d” , &a[i]) ;
buildnode (1 , 1 , n) ;

while (m--) {
    int opt ;
    scanf ("%d" , &opt) ;
    if (opt == 1) {
        int pos , val ;
        scanf ("%d%d" , &pos , &val) ; 
        modify (1 , pos , val) ;
        a[pos] = val ; 
    }
    else {
        int ql , qr , x ;
        scanf ("%d%d%d" , &ql , &qr , &x) ;
        cout << query (1 , ql , qr , x) << endl ;
    }
}   
return 0 ;

}



活动打卡代码 AcWing 2179. 圆桌问题

鹤萝芠
3个月前
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 3 , inf = 0x3f3f3f3f ;

int cur[N] , h[N] , cnt = 1 ;
int n , m , ALL ;
int q[N] , dep[N] ;


int S , T , ccnt ;
int num[275] , c[275][155] ;


struct ga {
    int to , nxt , f ;
}e[N << 1] ;

void add (int a , int b , int c) {
    e[++cnt] = {b , h[a] , c} , h[a] = cnt ;
}


bool bfs () {
    int hh = 0 , tt = 0 ;
    memset (dep , -1 , sizeof dep) ;
    q[0] = S , dep[S] = 0 , cur[S] = h[S] ;
    while (hh <= tt) {
        int u = q[hh++] ;
        for (int i = h[u] ; i ; i = e[i].nxt) {
            int t = e[i].to ;
            if (dep[t] == -1 && e[i].f) {
                dep[t] = dep[u] + 1 , cur[t] = h[t] ;
                if (t == T) return true ;
                else q[++tt] = t ;
            }
        }
    }
    return false ;
}

int find (int u , int lim) {
    if (u == T) return lim ;
    int part = 0 ;
    for (int i = cur[u] ; i && part < lim ; i = e[i].nxt) {
        int t = e[i].to ;
        cur[u] = i ;
        if (dep[t] == dep[u] + 1 && e[i].f) {
            int value = find (t , min (e[i].f , lim - part)) ;
            if (!value) dep[t] = -1 ;
            e[i ^ 1].f += value , e[i].f -= value , part += value ;
        }
    }
    return part ;
}


int dinic () {
    int sum = 0 , part = 0 ;
    while (bfs ()) while (part = find (S , inf)) sum += part ;
    return sum ;
} 

int main () {
    scanf ("%d%d" , &m , &n) ;
    S = 0 , T = n + m + 1 ;
    for (int i = 1 ; i <= m ; i ++) {
        int c ;
        scanf ("%d" , &c) ;
        add (S , i , c) , add (i , S , 0) ;
        ALL += c ;
    }
    for (int i = 1 ; i <= n ; i ++) {
        int c ;
        int node = i + m ;
        scanf ("%d" , &c) ;
        add (node , T , c) , add (T , node , 0) ;
    }
    for (int i = 1 ; i <= m ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            int node = m + j ;
            add (i , node , 1) , add (node , i , 0) ;
        }
    }
    if (dinic () != ALL) cout << 0 << endl ;
    else {
        cout << 1 << endl ;
        for (int i = 1 ; i <= m ; i ++) {
            for (int j = h[i] ; j ; j = e[j].nxt) {
                int t = e[j].to ;
                if (t != T && t != S && !e[j].f) {
                    printf ("%d " , t - m) ;
                }
            }
            cout << endl ;
        }
    }

    return 0 ;
}



鹤萝芠
3个月前
#include <bits/stdc++.h>
using namespace std ;
const int N = 105 + 5 , M = 1e5 + 5 , inf = 1e8 + 3 ;

struct ga {
    int to , nxt , f ;
}e[M] ;

int cnt = 1 , h[N] ;
int S , T ;

int n , m , dep[N] , cur[N] ;
int q[N] ;

void add (int a , int b , int c) {
    e[++cnt] = (ga) {b , h[a] , c} , h[a] = cnt ;
}

bool bfs () {
    memset (dep , -1 , sizeof dep); 
    int hh = 0 , tt = 0 ;
    q[0] = S , dep[S] = 0 , cur[S] = h[S] ;
    while (hh <= tt) {
        int u = q[hh ++] ;
        for (int i = h[u] ; i ; i = e[i].nxt) {
            int t = e[i].to ;
            if (dep[t] == -1 && e[i].f) {                
                dep[t] = dep[u] + 1 , cur[t] = h[t] ;
                if (t == T) return true ;
                else q[++tt] = t ;
            }
        }
    }
    return false ;
}


int find (int u , int lim) {
    if (u == T) return lim ;
    int flow = 0 ;
    for (int i = cur[u] ; i and flow < lim ; i = e[i].nxt) {
        int t = e[i].to ;
        cur[u] = i ;
        if (dep[t] == dep[u] + 1 && e[i].f) {
            int valt = find (t , min (e[i].f , lim - flow)) ;
            if (!valt) dep[t] = -1 ;
            e[i].f -= valt , e[i ^ 1].f += valt , flow += valt ;
        }
    }
    return flow ;
}

int dinic () {
    int part , sum = 0 ;
    while (bfs()) while (part = find (S , inf)) sum += part ;
    return sum ;
}


int main () {
    scanf ("%d%d" , &m , &n) ;
    int a , b ;
    while (scanf ("%d%d" , &a , &b) , a != -1) {
        add (a , b , 1) , add (b , a , 0) ;
    }
    S = 0 , T = n + 1 ;
    for (int i = 1 ; i <= m ; i ++) add (S , i , 1) , add (i , S , 0) ;
    for (int i = m + 1 ; i <= n ; i ++) add (i , T , 1) , add (T , i , 0) ;
    printf ("%d\n" , dinic ()) ;
    for (int i = 1 ; i <= m ; i ++) {
        for (int j = h[i] ; j ; j = e[j].nxt) {
            int t = e[j].to ;
            if (t <= n && t && !e[j].f) cout << i << " " << t << endl ;

        }
    }
    return 0 ;
}



鹤萝芠
3个月前
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 3 , inf = 0x3f3f3f3f ;

int dep[N] ;
int n , m , S , T ;
struct ga {
    int to , nxt , f ;
}e[N << 1] ;

int cnt = 1 , h[N] , cur[N] , q[N] ;


void add (int a , int b , int c) {
    e[++cnt] = (ga) {b , h[a] , c} , h[a] = cnt ;
}

bool bfs () {
    int hh = 0 , tt = 0 ;
    memset (dep , -1 , sizeof dep) ;
    dep[S] = inf , cur[S] = h[S] , q[0] = S ;
    while (hh <= tt) {
        int u = q[hh++] ;
        for (int i = h[u] ; i ; i = e[i].nxt) {
            int t = e[i].to ;
            if (dep[t] == -1 && e[i].f) {
                cur[t] = h[t] , dep[t] = dep[u] + 1 ;
                if (t == T) return true ;
                else q[++tt] = t ;
            }
        }
    }
    return false ;
}

int find (int u , int lim) {    
    if (u == T) return lim ;
    int flow = 0 ;
    for (int i = cur[u] ; i && flow < lim ; i = e[i].nxt) {
        int t = e[i].to ;
        cur[u] = i ;
        if (dep[t] == dep[u] + 1 && e[i].f) {
            int valt = find (t , min (e[i].f , lim - flow)) ;
            if (!valt) dep[t] = -1 ;
            e[i].f -= valt , e[i ^ 1].f += valt , flow += valt ;
        }
    }
    return flow ;
} 

int dinic () {
    int part , ans = 0 ;
    while (bfs()) while (part = find (S , inf)) ans += part ;
    return ans ;
} 

int main () {
    scanf ("%d%d%d%d" , &n , &m , &S , &T) ;

    for (int i = 1 ; i <= m ; i ++) {
        int a , b , c  ;
        scanf ("%d%d%d" , &a , &b , &c) ;
        add (a , b , c) ;
        add (b , a , 0) ;
    }
    printf ("%d" , dinic ()) ;
}


活动打卡代码 AcWing 2171. EK求最大流

鹤萝芠
3个月前
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 5 , inf = 0x3f3f3f3f ;


int S , T ;
int cnt = 1 , h[N] , n , m , Pre[N] ;
bool ark[N] ;
int d[N] , q[N] ;


struct ga {
    int to , nxt , f ;
}e[N << 1] ;

void add (int a , int b , int c) {
    e[++cnt].to = b , e[cnt].nxt = h[a] , h[a] = cnt , e[cnt].f = c ;
} 


bool bfs () {
    memset (ark , 0 , sizeof ark) ;
    int hh = 0 , tt = 0 ;
    d[S] = inf , q[0] = S , ark[S] = 1 ;
    while (hh <= tt) {
        int u = q[hh++] ;
        for (int i = h[u] ; i ; i = e[i].nxt) {
            int t = e[i].to ;
            if (ark[t] || !e[i].f) continue ;
            ark[t] = 1 , Pre[t] = i , d[t] = min (d[u] , e[i].f) ;
            if (t == T) return true ;
            else q[++tt] = t ;
        }

    }
    return false ;  
}

int EK () {
    int ans = 0 ;
    while (bfs()) {
        ans += d[T] ;
        for (int i = T ; i != S ; i = e[Pre[i] ^ 1].to) {
            e[Pre[i]].f -= d[T] , e[Pre[i] ^ 1].f += T ; 
        } 
    }
    return ans ;
}

int main () {
    scanf ("%d%d%d%d" , &n , &m , &S , &T) ;
    for (int i = 1 ; i <= m ; i ++) {
        int a , b , c ;
        cin >> a >> b >> c ;
        add (a , b , c) ;
        add (b , a , 0) ;
    }
    printf ("%d\n" , EK()) ;
    return 0 ;
}


活动打卡代码 AcWing 1125. 牛的旅行

鹤萝芠
3个月前
#include <bits/stdc++.h>
using namespace std ;
const int N = 155 ;
const double inf = 1e20 ;
typedef pair <int , int> PII ;

double d[N][N] , maxt[N] ;

int n , m ;
string g[N] ;
PII p[N] ;

double getd (PII a, PII b) {
    int dx = a.first - b.first , dy = a.second - b.second ;
    return sqrt (dx * dx + dy * dy) ;
}

int main () {
    cin >> n ;
    for (int i = 0 ; i < n ; i ++) cin >> p[i].first >> p[i].second ;
    for (int i = 0 ; i < n ; i ++) cin >> g[i] ;
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            if (i == j) {
                d[i][j] = 0 ;
            }
            else {
                if (g[i][j] == '1') d[i][j] = getd (p[i] , p[j]) ;
                else d[i][j] = inf ;
            }
        }
    }

    for (int k = 0 ; k < n ; k ++) {
        for (int i = 0 ; i < n ; i ++) {
            for (int j = 0 ; j < n ; j ++) {
                d[i][j] = min (d[i][j] , d[i][k] + d[k][j]) ;
            }
        }
    }
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            if (d[i][j] != inf) maxt[i] = max (maxt[i] , d[i][j]) ;
        }
    }
    double ans1 = 0 , ans2 = inf ;
    for (int i = 0 ; i < n ; i ++) ans1 = max (ans1 , maxt[i]) ;
    for (int i = 0 ; i < n ; i ++) {
        for (int j = 0 ; j < n ; j ++) {
            if (d[i][j] == inf) ans2 = min (ans2 , maxt[i] + maxt[j] + getd (p[i] , p[j])) ;
        }
    }
    double res = max (ans1 , ans2) ;
    printf ("%.6f" , res) ;



    return 0 ;
}



鹤萝芠
3个月前
#include<bits/stdc++.h>
using namespace std ;
#define GG getchar ()
const int N = 1e5 + 10 ;
typedef long long ll ;

int n , m , len ;
ll s[N] , w[N] , add[N] ;

int get (int i) {
    return (i - 1) / len ; 
}
void modify (int ql , int qr , int d) {
    if (get (ql) == get (qr)) {
        for (int i = ql ; i <= qr ; i ++) w[i] += d , s[get (i)] += d ; 
    }
    else {
        int i = ql , j = qr ;
        while (get (i) == get (ql)) w[i] += d , s[get (i)] += d , i ++ ;
        while (get (j) == get (qr)) w[j] += d , s[get (j)] += d , j -- ;
        for (int _ = get (i) ; _ <= get (j) ; _ ++) s[_] += len * d , add[_] += d ; 
    }
}
ll query (int ql , int  qr) {
    ll res = 0 ;
    if (get (ql) == get (qr)) {
        for (int i = ql ; i <= qr ; i ++) res += w[i] + add[get (i)] ;
    }
    else {
        int i = ql , j = qr ;
        while (get (i) == get (ql)) res += w[i] + add[get (i)] ,  i ++ ;
        while (get (j) == get (qr)) res += w[j] + add[get (j)] ,  j -- ;
        for (int _ = get (i) ; _ <= get (j) ; _ ++) res += s[_] ;
    }
    return res ;
}
int main () {
    cin >> n >> m ;
    len = sqrt (n) ;
    for (int i = 1 ; i <= n ; i ++) cin >> w[i] ;
    for (int i = 1 ; i <= n ; i ++) s[get(i)] += w[i] ;
    while (m --) {
        char opt ; int  ql , qr ;
        cin >> opt >> ql >> qr ;
        if (opt == 'C') {
            int d ;
            cin >> d ;
            modify (ql , qr , d) ;
        }
        else {
            cout << query (ql , qr) << endl ;

        }
    }
    return 0 ;
}


新鲜事 原文

鹤萝芠
3个月前
今天进阶课停课了一次吗 qwq