template

 1const int maxn = 2e5 + 10;
 2const int maxsize = 26;
 3struct TRIE{
 4    int ch[maxn][maxsize];
 5    int flag[maxn];
 6    int top = 1;
 7
 8    //按照实际条件进行修改
 9    inline int getid(char c){return c - 'a';}
10
11    //插入长度为n的字符串s[0,..n - 1]
12    void insert(char s[maxn], int n){
13        int u = 0;
14        for(int i = 0; i < n; i++){
15            int id = getid(s[i]);
16            if(!ch[u][id]) ch[u][id] = top++;
17            u = ch[u][id];
18        }
19        flag[u] = 1;
20    }
21
22    bool query(char s[maxn], int n){
23        int u = 0;
24        for(int i = 0; i < n; i++){
25            int id = getid(s[i]);
26            if(!ch[u][id]) return false;
27            u = ch[u][id];
28        }
29        if(flag[u]) return true; return false;
30    }
31};

 1const int maxn = 2e5 + 10;
 2const int maxsize = 26;
 3const int maxnode = maxn * maxsize;
 4struct TRIE{
 5//    vector<int> head, next;
 6//    vector<char> ch;
 7    int head[maxnode], next[maxnode];
 8    char ch[maxnode];
 9    bool flag[maxnode];
10    int top = 1;
11    
12    void insert(char s[maxn], int n){
13        int u = 0;
14        for(int i = 0; i < n; i++){
15            int find = 0, v;
16            for(v = head[u]; v; v = next[v]) if(ch[v] == s[i]){
17                find = 1; break;
18            }
19            if(!find){
20                v = top++;
21                ch[v] = s[i];
22                next[v] = head[u];
23                head[u] = v;
24            }
25            u = v;
26        }
27        flag[u] = 1;
28    }
29    
30    bool query(char s[maxn], int n){
31        int u = 0;
32        for(int i = 0; i < n; i++){
33            int find = 0;
34            for(int v = head[u]; v; v = next[v]) if(ch[v] == s[i]){
35                find = 1; u = v; break;
36            }
37            if(!find) return false;
38        }
39        if(flag[u]) return true; return false;
40    }
41};

 1/*
 2 Manacher算法
 3 读入一个字符串temp及其长度n;
 4 该算法构造出s并赋予截断标志, 自动初始化、获得数组p[i];
 5 对于某个位置i∈[0, 2 * n], 以i为中心的回文串的参数如下:
 6    int start = (i / 2) - (p[i] / 2) + (i & 1), d = p[i] - 1;
 7 */
 8int n;
 9char temp[maxn], s[maxn << 1];
10int p[maxn << 1];
11void manacher(){
12    //scanf("%s", temp);
13    for(int i = 0; i < n; i++){
14        s[i << 1] = '#'; s[i << 1 | 1] = temp[i];
15    }
16    s[n << 1] = '#'; s[n << 1 | 1] = 0;
17    
18    int id = 0, right = 0;
19    for(int i = 0; i <= n << 1; i++) p[i] = 1;
20    for(int i = 1; i <= n << 1; i++){
21        if(i <= right) p[i] = min(right - i + 1, p[2 * id - i]);
22        while(i + p[i] <= 2 * n && i - p[i] >= 0 && s[i + p[i]] == s[i - p[i]])
23            p[i]++;
24        if(right < i + p[i] - 1){
25            id = i; right = i + p[i] - 1;
26        }
27    }
28}

 1const int maxn = 2e5 + 10;
 2const int N = 30;
 3
 4char s[maxn * 10];
 5int ch[maxn][N], top = 1;
 6int fail[maxn];
 7
 8int pos[maxn];
 9
10void insert(char *s, int id){
11    int p = 0;
12    for(int i = 0; s[i]; i++){
13        if(!ch[p][s[i] - 'a']) ch[p][s[i] - 'a'] = top++;
14        p = ch[p][s[i] - 'a'];
15    }
16    pos[id] = p;
17}
18
19queue<int> q;
20void getfail(){
21    for(int i = 0; i < N; i++) if(ch[0][i]){
22        fail[ch[0][i]] = 0;
23        q.push(ch[0][i]);
24    }
25    while(!q.empty()){
26        int now = q.front(); q.pop();
27        for(int i = 0; i < N; i++){
28            if(ch[now][i]){
29                fail[ch[now][i]] = ch[fail[now]][i];
30                q.push(ch[now][i]);
31            }
32            else ch[now][i] = ch[fail[now]][i];
33        }
34    }
35}
36
37struct star{int to, next;}edge[maxn];
38int head[maxn], _top = 0, sze[maxn];
39void add(int u, int v){
40    edge[_top].to = v;
41    edge[_top].next = head[u];
42    head[u] = _top++;
43}
44
45void dfs(int now){
46    for(int i = head[now]; ~i; i = edge[i].next){
47        int to = edge[i].to; dfs(to);
48        sze[now] += sze[to];
49    }
50}
51
52
53int main(){
54//    Fastin;
55    clr(head, -1);
56    int n; scanf("%d", &n);
57    for(int i = 1; i <= n; i++){
58        scanf("%s", s); insert(s, i);
59    }
60    getfail();
61    
62    scanf("%s", s);
63    for(int i = 0, p = 0; s[i]; i++){
64        p = ch[p][s[i] - 'a'];
65        sze[p]++;
66    }
67    
68    for(int i = 1; i < top; i++) add(fail[i], i); dfs(0);
69    for(int i = 1; i <= n; i++) printf("%d\n", sze[pos[i]]);
70    
71    return 0;
72}

 1const int maxn = 3e5 + 10;
 2const int N = 26 + 10;
 3char s[maxn];
 4
 5int len[maxn], fail[maxn];
 6int ch[maxn][N], top;
 7
 8void ini(){fail[1] = fail[0] = 1; len[1] = -1; top = 2;}
 9
10//插入字符s[n]
11int getfail(int x, int n){
12    while(s[n - 1 - len[x]] != s[n]) x = fail[x];
13    return x;
14}
15
16//下标从1开始
17void build(char s[maxn]){
18    ini();
19    //选取一个保证不会出现的字符。
20    s[0] = -1;
21    //last维护了以s[n - 1]结尾的最长回文子串的节点标号。
22    int last = 0;
23    for(int i = 1; s[i]; i++){
24        s[i] -= 'a';
25        int p = getfail(last, i);
26        if(!ch[p][s[i]]){
27            len[top] = len[p] + 2;
28            fail[top] = ch[getfail(fail[p], i)][s[i]];
29            ch[p][s[i]] = top;
30            top++;
31        }
32        last = ch[p][s[i]];
33    }
34}

 1const int manx = 1e2 + 10;
 2const double eps = 1e-8;
 3const double pi = acos(-1);
 4
 5inline int sgn(double x){return x < -eps? -1: x > eps? 1: 0;}
 6inline double sqr(double x){return x * x;}
 7
 8struct CIRCLE{
 9    double x, y, r, angle;
10    int d;
11    CIRCLE(){d = 1; angle = 0;}
12    CIRCLE(double _x, double _y, double _angle = 0, int _d = 0){
13        x = _x; y = _y; angle = _angle; d = _d; r = 0;
14    }
15    bool operator < (const CIRCLE &b)const{
16        return sgn(r - b.r) == -1;
17    }
18};
19
20inline double dis(CIRCLE a, CIRCLE b){return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
21inline double cross(CIRCLE a, CIRCLE b, CIRCLE c){
22    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
23}
24
25//有两个交点返回true，以及两个交点的坐标和方位角，p1按照顺时针，p2按照逆时针
26bool cir_inter_cir(CIRCLE a, CIRCLE b, CIRCLE &p1, CIRCLE &p2){
27    double d = dis(a, b);
28    if(sgn(d - a.r - b.r) >= 0 || sgn(abs(b.r - a.r) - d) >= 0) return false;
29    double cosa = (sqr(a.r) + sqr(d) - sqr(b.r)) / (2 * a.r * d);
30    double sina = sqrt(max(0., 1. - sqr(cosa)));
31    //旋转矩阵 [cosa, -sina; sina, cosa]
32    p1 = p2 = a;
33    p1.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * -sina);
34    p1.y += a.r / d * ((b.x - a.x) * sina + (b.y - a.y) * cosa);
35    p2.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * sina);
36    p2.y += a.r / d * ((b.x - a.x) * -sina + (b.y - a.y) * cosa);
37    return true;
38}
39
40bool cmp(const CIRCLE &a, const CIRCLE &b){
41    if(sgn(a.angle - b.angle)) return sgn(a.angle - b.angle) == -1;
42    else return a.d > b.d;
43}
44
45double cal(CIRCLE a, CIRCLE p1, CIRCLE p2){
46    double ans = sqr(a.r) * (p2.angle - p1.angle) - cross(a, p1, p2) + cross(CIRCLE(0, 0), p1, p2);
47    return ans / 2;
48}
49
50CIRCLE dot[maxn << 1];
51double area[maxn];
52void cirunion(CIRCLE cir[], int n){
53    sort(cir, cir + n);
54    //记录每个圆被完全覆盖的次数，初始值显然为1
55    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
56        if(sgn(dis(cir[i], cir[j]) + cir[i].r - cir[j].r) <= 0) cir[i].d++;
57    CIRCLE p1, p2;
58    for(int i = 0; i < n; i++){
59        //针对每一个圆考虑它与所有其他圆的交
60        int cnt = 0, top = 0;
61        for(int j = 0; j < n; j++){
62            if(i == j) continue;
63            if(!cir_inter_cir(cir[i], cir[j], p1, p2)) continue;
64            p1.angle = atan2(p1.y - cir[i].y, p1.x - cir[i].x);
65            p2.angle = atan2(p2.y - cir[i].y, p2.x - cir[i].x);
66            p1.d = -1; p2.d = 1;
67            dot[top++] = p1; dot[top++] = p2;
68            if(sgn(p2.angle - p1.angle) == 1) cnt++;
69        }
70        
71        //加入起点终点位置
72        dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, -pi, -2);
73        dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, pi, 2);
74        sort(dot, dot + top, cmp);
75        int now = cir[i].d + cnt;
76        for(int j = 1; j < top; j++){
77            area[now] += cal(cir[i], dot[j - 1], dot[j]);
78            now += dot[j].d;
79        }
80    }
81}
82
83CIRCLE cir[maxn];
84int main(){
85//    Fastin;
86    int t; scanf("%d", &t); while(t--){
87        clr(area, 0);
88        int n; scanf("%d", &n);
89        for(int i = 0; i < n; i++) scanf("%lf %lf %lf", &cir[i].x, &cir[i].y, &cir[i].r);
90        cirunion(cir, n);
91        for(int i = 1; i <= n; i++) printf("%.5f\n", area[i]);
92    }
93    return 0;
94}

 1const int maxn = 1e2 + 10;
 2const double eps = 1e-9;
 3
 4struct POINT{
 5    double x, y;
 6    POINT operator - (const POINT &b){
 7        POINT temp;
 8        temp.x = x - b.x;
 9        temp.y = y - b.y;
10        return tmep;
11    }
12}p[maxn];
13
14double cross(POINT a, POINT b){ return a.x * b.y - a.y * b.x;}
15double dis(POINT a){return sqrt(a.x * a.x + a.y * a.y);}
16int sgn(double x){return x < -eps? -1: x > eps? 1: 0;}
17bool cmp(POINT a, POINT b){
18    int flag = sgn(cross(a, b));
19    if(flag == 0) return dis(a) < dis(b);
20    else return flag == 1;
21}
22
23int sta[maxn], top = 0;
24void push(int x){sta[top++] = x;}
25
26int main(){
27    // Fastin;
28    int n; while(~scnaf("%d", &n) && n){
29        top = 0; int id = -1;
30        for(int i = 1; i <= n ; i++){
31            int x, y; scnaf("%d %d", &x, &y);
32            p[i].x = x; p[i].y = y;
33            if(id == -1 || (p[id].x > p[i].x) || (p[id].x == p[i].x && p[id].y > p[i].y)) id = i;
34        }
35
36        //不特判计算几何的都是xx!
37        if(n == 1){puts("0.00"); continue;}
38        if(n == 2){printf("%.2f\n", dis(p[1] - p[2])); continue;}
39
40        for(int i = 1; i <= n; i++) if(i != id) p[i] = p[i] - p[id];
41        p[id].x = p[id].y = 0;
42        sort(p + 1, p + 1 + n, cmp);
43
44        push(1); push(2);
45        for(int i = 3; i <= n; i++){
46            while(1){
47                if(sgn(cross(p[i] - p[sta[top - 2]], p[i] - p[sta[top - 1]])) >= 0){
48                    push(i); break;
49                }
50                else top--;
51            }
52        }
53
54        double ans = 0;
55        for(int i = 1; i < top; i++) ans += dis(p[sta[i]] - p[sta[i - 1]]);
56        ans += dis(p[sta[0]] - p[sta[top - 1]]);
57        printf("%.2f\n", ans);
58    }
59    return 0;
60}

 1const int maxn = 2e5 + 10;
 2
 3star edge[maxn << 1];
 4int head[manx], top = 0;
 5
 6void add(int u, int v){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    head[u] = top++;
10}
11
12stack<int> sta;
13int dfn[maxn], low[maxn], cnt = 1, in[maxn];
14void tarjan(int u){
15
16    dfn[u] = low[u] = cnt++;
17    sta.push(u); in[u] = 1;
18    for(int i = head[u]; ~i; i = edge[i].next){
19        int to = edge[i].to;
20        if(!dfn[to]){
21            tarjan(to);
22            low[u] = min(low[to], low[u]);
23        }
24        else if(in[to]){
25            low[u] = min(low[u], dfn[to]);
26        }
27    }
28
29    //输出以u节点为根的scc
30    if(dfn[u] == low[u]){
31        while(1){
32            assert(!sta.empty());
33
34            int v = sta.top(); sta.pop();
35            printf("%d ", v); in[v] = 0;
36
37            if(v == u){puts(""); break;}
38        }
39    }
40}
41
42int main(){
43    // Fastin;
44    clr(head, -1);
45    int n, m; scanf("%d %d", &n, &m);
46    for(int i = 0 ; i< m; i++){
47        int u, v; scanf("%d %d", &u, &v);
48        add(u, v);
49    }
50
51    tarjan(1);
52    return 0;
53}

 1const int maxn = 2e5 + 10;
 2const int N = 30;
 3const int inf = ~0u >> 1;
 4
 5int n, w[maxn], c[maxn];;
 6
 7int ch[maxn * N][2], sze = 1;
 8
 9void insert(int x){
10    int p = 0;
11    for(int i = N - 1; i >= 0; i--){
12        int id = (x >> i) & 1;
13        if(ch[p][id] == 0) ch[p][id] = sze++;
14        p = ch[p][id];
15    }
16}
17
18int query(int x){
19    int p = 0, ans = 0;
20    for(int i = N - 1; i >= 0; i--){
21        int id = (x >> i) & 1;
22        if(ch[p][id] > 0) p = ch[p][id];
23        else{
24            ans |= 1 << i;
25            p = ch[p][id ^ 1];
26        }
27    }
28    return ans;
29}
30
31ll ans = 0;
32void sove(int d, int l, int r){
33    if(l < 1 || r > n || l > r || d < 0) return;
34    
35    int L = l - 1, R = r + 1;
36    for(int i = l; i <= r; i++)
37        if(w[i] & 1 << d) c[--R] = w[i];
38        else c[++L] = w[i];
39    for(int i = l; i <= r; i++) w[i] = c[i];
40    
41    sove(d - 1, l, L);
42    sove(d - 1, R, r);
43    if(L < l || R > r) return;
44    
45    for(int i = l; i <= L; i++) insert(w[i]);
46    int m = inf;
47    for(int i = R; i <= r; i++) m = min(m, query(w[i]));
48    ans += m;
49    
50    for(int i = 0; i < sze; i++) ch[i][0] = ch[i][1] = 0;
51    sze = 1;
52}
53
54int main(){
55//    Fastin;
56    scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", w + i);
57    sove(N - 1, 1, n);
58    printf("%lld\n", ans);
59    return 0;
60}

 1const int manx = 510;
 2
 3int n, n1, n2, m;
 4int head[maxn << 1], top = 0;
 5struct star{int to, next;};
 6star edge[maxn * maxn];
 7void add(int u, int v){
 8    edge[top].to = v;
 9    edge[top].next = head[u];
10    head[u] = top++;
11}
12
13int vis[maxn << 1], match[maxn << 1];
14bool find(int u){
15    for(int i = head[u]; ~i; i = edge[i].next) if(!vis[edge[i].to]){
16        int to = edge[i].to; vis[to] = 1;
17        if(!match[to] || find(match[to])){
18            match[to] = u;
19            return 1;
20        }
21    }
22    return 0;
23}
24
25
26int hungary(){
27    int ans = 0;
28    for(int i = 1; i <= n; i++){
29        clr(vis, 0);
30        if(find(i)) ans++;
31    }
32    return ans;
33}
34
35int ans[maxn];
36
37int main(){
38//    Fastin;
39    clr(head, -1);
40 		//读入n1, n2, m, 表示两边点集的数量和边数，取n = max(n1, n2)作为序号的偏移量。
41    scanf("%d %d %d", &n1, &n2, &m); n = max(n1, n2);
42    for(int i = 0; i < m; i++){
43        int u, v; scanf("%d %d", &u, &v);
44        add(u, v + n);
45    }
46    
47    printf("%d\n", hungary());
48    for(int i = 1; i <= n2; i++) ans[match[i + n]] = i;
49    prt(ans + 1, n1);
50    return 0;
51}

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star {
 6    int to, next, w;
 7};
 8int head[maxn], top = 0;
 9star edge[maxe << 1];
10
11void add(int u, int v, int w) {
12    edge[top].to = v;
13    edge[top].next = head[u];
14    edge[top].w = w;
15    head[u] = top++;
16}
17
18int d[maxn], cur[maxn];
19ll dfs(int s, int t, ll flow) {
20    if (flow == 0 || s == t)
21        return flow;
22
23    ll res = 0, f;
24    for (int i = cur[s]; ~i; i = edge[i].next) {
25        cur[s] = i;
26        if (d[edge[i].to] == d[s] + 1) {
27            f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
28            edge[i].w -= f;
29            edge[i ^ 1].w += f;
30            res += f;
31            flow -= f;
32            if (flow == 0)
33                break;
34        }
35    }
36    return res;
37}
38
39queue<int> q, q0;
40bool bfs(int s, int t) {
41    clr(d, 0);
42    q = q0;
43    q.push(s);
44    cur[s] = head[s];
45    d[s] = 1;
46    while (!q.empty()) {
47        int now = q.front();
48        q.pop();
49        for (int i = head[now]; ~i; i = edge[i].next)
50            if (!d[edge[i].to] && edge[i].w > 0) {
51                cur[edge[i].to] = head[edge[i].to];
52                d[edge[i].to] = d[now] + 1;
53                if (edge[i].to == t)
54                    return true;
55                q.push(edge[i].to);
56            }
57    }
58    return false;
59}
60
61ll dinic(int s, int t) {
62    ll ans = 0;
63    while (bfs(s, t)) ans += dfs(s, t, inf);
64    return ans;
65}
66
67
68int main(){
69//    Fastin;
70    clr(head, -1);
71     //读入n1, n2, m, 表示两边点集的数量和边数，取n = max(n1, n2)作为序号的偏移量。
72    int n1, n2, m, n;
73    scanf("%d %d %d", &n1, &n2, &m); n = max(n1, n2);
74    for(int i = 0; i < m; i++){
75        int u, v; scanf("%d %d", &u, &v);
76        add(u, v + n, 1);
77        add(v + n, u, 0);
78    }
79    for(int i = 1; i <= n1; i++){add(0, i, 1); add(i, 0, 0);}
80    for(int i = 1; i <= n2; i++){add(i + n, 2 * n + 1, 1); add(2 * n + 1, i + n, 0);}
81    
82    printf("%lld\n", dinic(0, 2 * n + 1));
83    return 0;
84}

 1const int maxn = 410;
 2const int inf = 0x3f3f3f3f;
 3int a[maxn][maxn];
 4
 5int n;
 6int match[maxn];
 7int ex[2][maxn], vis[2][maxn];;
 8int slack[maxn];
 9
10int dfs(int now){
11    vis[0][now] = 1;
12    for(int i = 0; i < n; i++) if(!vis[1][i]){
13        int gap = ex[0][now] + ex[1][i] - a[now][i];
14        if(gap == 0){
15            vis[1][i] = 1;
16            if(match[i] == -1 || dfs(match[i])){ match[i] = now; return 1; }
17        }
18        else slack[i] = min(slack[i], gap);
19    }
20    return 0;
21}
22
23ll km(){
24    for(int i = 0; i < n; i++){match[i] = -1; ex[0][i] = ex[1][i] = 0;}
25    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) ex[0][i] = max(ex[0][i], a[i][j]);
26    
27    for(int i = 0; i < n; i++){
28        for(int i = 0; i < n; i++) slack[i] = inf;
29        
30        for(int i = 0; i < n; i++) vis[0][i] = vis[1][i] = 0;
31        if(dfs(i)) continue;
32        while(1){
33            int d = inf; for(int i = 0; i < n; i++) if(!vis[1][i]) d = min(d, slack[i]);
34            int pos = -1;
35            for(int i = 0; i < n; i++){
36                if(vis[0][i]) ex[0][i] -= d;
37                if(vis[1][i]) ex[1][i] += d;
38                else{
39                    slack[i] -= d;
40                    if(slack[i] == 0) pos = i;
41                }
42            }
43            assert(pos != -1);
44            if(match[pos] == -1) break;
45            int u = match[pos];
46            vis[0][u] = vis[1][pos] = 1;
47            for(int i = 0; i < n; i++) if(!vis[1][i]) slack[i] = min(slack[i], ex[0][u] + ex[1][i] - a[u][i]);
48        }
49        for(int i = 0; i < n; i++) vis[0][i] = vis[1][i] = 0;
50        dfs(i);
51    }
52    ll res = 0;
53    for(int i = 0; i < n; i++) res += a[match[i]][i];
54    return res;
55}
56
57int ans[maxn];
58int main(){
59//    Fastin;
60    int n1, n2, m; scanf("%d %d %d", &n1, &n2, &m);
61    n = max(n1, n2);
62    for(int i = 0; i < m; i++){
63        int u, v, w; scanf("%d %d %d", &u, &v, &w);
64        u--; v--; a[u][v] = w;
65    }
66    printf("%lld\n", km());
67    
68    for(int i = 0; i < n2; i++){
69        if(match[i] == -1) continue;
70        if(a[match[i]][i] == 0) ans[match[i]] = 0;
71        else ans[match[i]] = i + 1;
72    }
73    for(int i = 0; i < n1; i++) printf("%d ", ans[i]);
74    printf("\n");
75    return 0;
76}

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star {
 6    int to, next, w;
 7};
 8int head[maxn], top = 0;
 9star edge[maxe << 1];
10
11void add(int u, int v, int w) {
12    edge[top].to = v;
13    edge[top].next = head[u];
14    edge[top].w = w;
15    head[u] = top++;
16}
17
18int d[maxn], cur[maxn];
19
20ll dfs(int s, int t, ll flow) {
21    if (flow == 0 || s == t)
22        return flow;
23
24    ll res = 0, f;
25    for (int i = cur[s]; ~i; i = edge[i].next) {
26        cur[s] = i;
27        if (d[edge[i].to] == d[s] + 1) {
28            f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
29            edge[i].w -= f;
30            edge[i ^ 1].w += f;
31            res += f;
32            flow -= f;
33            if (flow == 0)
34                break;
35        }
36    }
37    return res;
38}
39
40queue<int> q, q0;
41bool bfs(int s, int t) {
42    clr(d, 0);
43    q = q0;
44    q.push(s);
45    cur[s] = head[s];
46    d[s] = 1;
47    while (!q.empty()) {
48        int now = q.front();
49        q.pop();
50        for (int i = head[now]; ~i; i = edge[i].next)
51            if (!d[edge[i].to] && edge[i].w > 0) {
52                cur[edge[i].to] = head[edge[i].to];
53                d[edge[i].to] = d[now] + 1;
54                if (edge[i].to == t)
55                    return true;
56                q.push(edge[i].to);
57            }
58    }
59    return false;
60}
61
62ll dinic(int s, int t) {
63    ll ans = 0;
64    while (bfs(s, t)) ans += dfs(s, t, inf);
65    return ans;
66}
67
68int main() {
69    //    Fastin;
70    clr(head, -1);
71    int n, m, s, t;
72    scanf("%d %d %d %d", &n, &m, &s, &t);
73    for (int i = 0, u, v, w; i < m; i++) {
74        scanf("%d %d %d", &u, &v, &w);
75        add(u, v, w);
76        add(v, u, 0);
77    }
78    printf("%lld\n", dinic(s, t));
79    return 0;
80}

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star {
 6    int to, next, w;
 7};
 8int n, m, s, t;
 9int head[maxn], top = 0;
10star edge[maxe << 1];
11
12void add(int u, int v, int w) {
13    edge[top].to = v;
14    edge[top].next = head[u];
15    edge[top].w = w;
16    head[u] = top++;
17}
18
19int d[maxn], cur[maxn], gap[maxn];
20
21queue<int> q;
22void bfs(int s, int t) {
23    q.push(t);
24    gap[d[t] = 1]++;
25    cur[t] = head[t];
26    while (!q.empty()) {
27        int now = q.front();
28        q.pop();
29        for (int i = head[now]; ~i; i = edge[i].next)
30            if (!d[edge[i].to]) {
31                gap[d[edge[i].to] = d[now] + 1]++;
32                cur[edge[i].to] = head[edge[i].to];
33                q.push(edge[i].to);
34            }
35    }
36}
37
38ll dfs(int x, int s, int t, ll flow) {
39    if (x == t)
40        return flow;
41
42    ll res = 0, f;
43    for (int i = cur[x]; ~i; i = edge[i].next) {
44        cur[x] = i;
45        if (d[x] == d[edge[i].to] + 1) {
46            f = dfs(edge[i].to, s, t, min(flow, (ll)edge[i].w));
47            edge[i].w -= f;
48            edge[i ^ 1].w += f;
49            flow -= f;
50            res += f;
51            if (flow == 0)
52                return res;
53        }
54    }
55    if (!(gap[d[x]]--))
56        d[s] = n + 1;
57    gap[++d[x]]++;
58    cur[x] = head[x];
59    return res;
60}
61
62ll isap(int s, int t) {
63    bfs(s, t);
64    ll ans = dfs(s, s, t, inf);
65    while (d[s] <= n) ans += dfs(s, s, t, inf);
66    return ans;
67}
68
69int main() {
70    //    Fastin;
71    clr(head, -1);
72    scanf("%d %d %d %d", &n, &m, &s, &t);
73    for (int i = 0, u, v, w; i < m; i++) {
74        scanf("%d %d %d", &u, &v, &w);
75        add(u, v, w);
76        add(v, u, 0);
77    }
78    printf("%lld\n", isap(s, t));
79    return 0;
80}

  1#include <bits/stdc++.h>
  2#define ll long long
  3using namespace std;
  4const int inf = INT_MAX;
  5const ll INF = (0x3f3f3f3f3f3f3f3fll);
  6const int maxn = 1.2e3 + 5;
  7struct HLPP {
  8    struct Edge {
  9        int v, rev;
 10        ll cap;
 11    };
 12    int n, sp, tp, lim, ht, lcnt;
 13    ll exf[maxn];
 14    vector<Edge> G[maxn];
 15    vector<int> hq[maxn], gap[maxn], h, sum;
 16    void init(int nn, int s, int t) {
 17        sp = s, tp = t, n = nn, lim = n + 1, ht = lcnt = 0;
 18        for (int i = 1; i <= n; ++i) G[i].clear(), exf[i] = 0;
 19    }
 20    void add_edge(int u, int v, ll cap) {
 21        G[u].push_back({ v, int(G[v].size()), cap });
 22        G[v].push_back({ u, int(G[u].size()) - 1, 0 });
 23    }
 24    void update(int u, int nh) {
 25        ++lcnt;
 26        if (h[u] != lim)
 27            --sum[h[u]];
 28        h[u] = nh;
 29        if (nh == lim)
 30            return;
 31        ++sum[ht = nh];
 32        gap[nh].push_back(u);
 33        if (exf[u] > 0)
 34            hq[nh].push_back(u);
 35    }
 36    void relabel() {
 37        queue<int> q;
 38        for (int i = 0; i <= lim; ++i) hq[i].clear(), gap[i].clear();
 39        h.assign(lim, lim), sum.assign(lim, 0), q.push(tp);
 40        lcnt = ht = h[tp] = 0;
 41        while (!q.empty()) {
 42            int u = q.front();
 43            q.pop();
 44            for (Edge &e : G[u])
 45                if (h[e.v] == lim && G[e.v][e.rev].cap)
 46                    update(e.v, h[u] + 1), q.push(e.v);
 47            ht = h[u];
 48        }
 49    }
 50    void push(int u, Edge &e) {
 51        if (!exf[e.v])
 52            hq[h[e.v]].push_back(e.v);
 53        ll df = min(exf[u], e.cap);
 54        e.cap -= df, G[e.v][e.rev].cap += df;
 55        exf[u] -= df, exf[e.v] += df;
 56    }
 57    void discharge(int u) {
 58        int nh = lim;
 59        if (h[u] == lim)
 60            return;
 61        for (Edge &e : G[u]) {
 62            if (!e.cap)
 63                continue;
 64            if (h[u] == h[e.v] + 1) {
 65                push(u, e);
 66                if (exf[u] <= 0)
 67                    return;
 68            } else if (nh > h[e.v] + 1)
 69                nh = h[e.v] + 1;
 70        }
 71        if (sum[h[u]] > 1)
 72            update(u, nh);
 73        else {
 74            for (; ht >= h[u]; gap[ht--].clear())
 75                for (int &i : gap[ht]) update(i, lim);
 76        }
 77    }
 78    ll hlpp() {
 79        exf[sp] = INF, exf[tp] = -INF, relabel();
 80        for (Edge &e : G[sp]) push(sp, e);
 81        for (; ~ht; --ht) {
 82            while (!hq[ht].empty()) {
 83                int u = hq[ht].back();
 84                hq[ht].pop_back();
 85                discharge(u);
 86                if (lcnt > (n << 2))
 87                    relabel();
 88            }
 89        }
 90        return exf[tp] + INF;
 91    }
 92} hp;
 93signed main() {
 94    ios::sync_with_stdio(false);
 95    cin.tie(0), cout.tie(0);
 96    int n, m, s, t, u, v, w;
 97    cin >> n >> m >> s >> t;
 98    hp.init(n, s, t);
 99    while (m--) {
100        cin >> u >> v >> w;
101        hp.add_edge(u, v, w);
102    }
103    cout << hp.hlpp() << '\n';
104    return 0;
105}

 1const ll inf = 0x3f3f3f3f3f3f3f3f;
 2const int maxn = 410;
 3const int maxe = 2e4 + 10;
 4struct star{
 5    int from, to, next; ll c, w;
 6};
 7int n, m;
 8int head[maxn], top = 0;
 9star edge[maxe << 1];
10
11void add(int u, int v, int c, int w){
12    edge[top].from = u;
13    edge[top].to = v;
14    edge[top].c = c;
15    edge[top].w = w;
16    edge[top].next = head[u];
17    head[u] = top++;
18}
19
20ll dis[maxn], h[maxn];
21int pre[maxn];
22struct NODE{
23    int u; ll d;
24    bool operator <(const NODE &b)const{
25        return d > b.d;
26    }
27};
28priority_queue<NODE> pq, pq0;
29ll mcmf(int s, int t, ll f, ll &flow){
30    ll res = 0;
31    while(f){
32        clr(dis, 0x3f); dis[s] = 0;
33        pq = pq0; pq.push({s, dis[s]});
34        while(!pq.empty()){
35            NODE temp = pq.top(); pq.pop();
36            int u = temp.u; ll d = temp.d;
37            if(dis[u] < d) continue;
38            for(int i = head[u]; ~i; i = edge[i].next){
39                int to = edge[i].to;
40                if(edge[i].c > 0 && dis[to] > dis[u] + edge[i].w + h[u] - h[to]){
41                    dis[to] = dis[u] + edge[i].w + h[u] - h[to];
42                    pre[to] = i;
43                    pq.push({to, dis[to]});
44                }
45            }
46        }
47        if(dis[t] == inf) break;
48        for(int i = 1; i <= n; i++) h[i] += dis[i];
49        
50        ll d = f;
51        for(int now = t; now != s; now = edge[pre[now]].from) d = min(d, edge[pre[now]].c);
52        for(int now = t; now != s; now = edge[pre[now]].from){
53            edge[pre[now]].c -= d;
54            edge[pre[now] ^ 1].c += d;
55        }
56        f -= d; flow += d; res += d * h[t];
57    }
58    return res;
59}
60
61int main(){
62//    Fastin;
63    clr(head, -1);
64    scanf("%d %d", &n, &m);
65    for(int i = 0; i < m; i++){
66        int u, v, c, w; scanf("%d %d %d %d", &u, &v, &c, &w);
67        add(u, v, c, w); add(v, u, 0, -w);
68    }
69    ll flow = 0;
70    ll res = mcmf(1, n, inf, flow);
71    printf("%lld %lld\n", flow, res);
72    return 0;
73}

 1#define mid ((l + r) >> 1)
 2
 3const int maxn = 5e5 + 10;
 4const int maxe = 4e7 + 10;
 5int M;
 6
 7int n, m, p;
 8struct {int to, next, w;}edge[maxe];
 9int head[maxe], top = 0;
10void add(int u, int v, int w){
11    edge[top].to = v;
12    edge[top].w = w;
13    edge[top].next = head[u];
14    head[u] = top++;
15}
16
17
18int cnt = 0, pos[maxn], ls[maxn << 3], rs[maxn << 3];
19int build(int l, int r){
20    int now = cnt++;
21    if(l == r){
22        add(now, now + M, 0);
23        return pos[l] = now;
24    }
25    ls[now] = build(l, mid);
26    add(now, ls[now], 0); add(ls[now] + M, now + M, 0);
27    rs[now] = build(mid + 1, r);
28    add(now, rs[now], 0); add(rs[now] + M, now + M, 0);
29    return now;
30}
31
32
33void update(int p, int l, int r, int L, int R, int u, int type){
34    if(L <= l && r <= R){
35        if(type) add(p + M, u, 1); else add(u, p, 0);
36        return ;
37    }
38    if(L <= mid) update(ls[p], l, mid, L, R, u, type);
39    if(R > mid) update(rs[p], mid + 1, r, L, R, u, type);
40}
41
42int dis[5000000];
43deque<int> q;
44void bfs(){
45    clr(dis, 0x3f);
46    while(!q.empty()) q.pop_back();
47    
48    dis[pos[p]] = 0; q.push_back(pos[p]);
49    while(!q.empty()){
50        int now = q.front(); q.pop_front();
51        
52        for(int i = head[now]; ~i; i = edge[i].next){
53            int to = edge[i].to; if(dis[to] != 0x3f3f3f3f) continue;
54            dis[to] = dis[now] + edge[i].w;
55            if(edge[i].w) q.push_back(to);
56            else q.push_front(to);
57        }
58    }
59}
60
61
62int main(){
63//    Fastin;
64    clr(head, -1);
65    scanf("%d %d %d", &n, &m, &p);
66    M = n << 2; build(1, n);
67    for(int i = 0; i < m; i++){
68        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
69        //加入虚点i + 2M与i + 1 + 2M;
70        update(0, 1, n, a, b, 2 * i + 2 * M, 1); update(0, 1, n, c, d, 2 * i + 2 * M, 0);
71        update(0, 1, n, c, d, 2 * i + 2 * M + 1, 1); update(0, 1, n, a, b, 2 * i + 2 * M + 1, 0);
72    }
73    bfs();
74    for(int i = 1; i <= n; i++) printf("%d\n", dis[pos[i]]);
75    return 0;
76}

 1const int N = 30;
 2const itn maxn = 1e5 * N  +10;
 3struct TRIE{
 4    int version = 0, top = 0;
 5    int ch[maxn][2], root[maxn];;
 6    
 7    void insert(int x){
 8        int rot = root[version];
 9        root[++version] = ++top;
10        for(int i = N - 1; i >= 0; i--){
11            int id = (x >> i) & 1;
12            ch[top][id] = top + 1; //新建
13            ch[top][!id] = ch[rot][!id]; //继承
14            top++; rot = ch[rot][id];
15        }
16    }
17};

 1const int N = 24;
 2const itn maxn = 1e5  +10;
 3
 4struct TRIE{
 5    int version = 0, top = 0;
 6    int ch[maxn][2], root[maxn];;
 7    int size[maxn];
 8    
 9    void insert(int x){
10        int rot = root[version];
11        root[++version] = ++top;
12        for(int i = N - 1; i >= 0; i--){
13            int id = (x >> i) & 1;
14            ch[top][id] = top + 1;
15            ch[top][!id] = ch[rot][!id];
16            size[top] = size[rot] + 1;
17            top++; rot = ch[rot][id];
18        }
19        size[top] = size[rot] + 1;
20    }
21    
22  	//查找[L + 1, R]的结果
23    int query(int L, int R, itn x){
24        int l = root[L], r = root[R];
25        int ans = 0;
26        for(int i = N - 1; i >= 0; i--){
27            int id = (x >> i) & 1;
28            if(size[ch[r][!id]] - size[ch[l][!id]] > 0){
29                ans |= 1 << i;
30                r = ch[r][!id]; l = ch[l][!id];
31            }
32            else{
33                r = ch[r][id];
34                l = ch[l][id];
35            }
36        }
37        return ans;
38    }
39};

 1#define mid ((l + r) >> 1)
 2const int maxn = 2e5 + 10;
 3const int N = 5;
 4int a[maxn], c[maxn];
 5unordered_map<int, int> mp;
 6int ls[maxn << N], rs[maxn << N], root[maxn], num[maxn << N], top = 0;
 7
 8int build(int l, int r){
 9    int p = top++;
10    if(l == r) return p;
11    ls[p] = build(l, mid);
12    rs[p] = build(mid + 1, r);
13    return p;
14}
15
16int update(int p, int l, int r, int k){
17    int now = top++;
18    ls[now] = ls[p]; rs[now] = rs[p]; num[now] = num[p] + 1;
19    if(l == r) return now;
20    if(k <= mid) ls[now] = update(ls[p], l, mid, k);
21    else rs[now] = update(rs[p], mid + 1, r, k);
22    return now;
23}
24
25int query(int r1, int r2, int l, int r, int k){
26    //[L + 1, R]
27    if(l == r) return l;
28    
29    int x = num[ls[r2]] - num[ls[r1]];
30    if(k <= x) return query(ls[r1], ls[r2], l, mid, k);
31    else return query(rs[r1], rs[r2], mid + 1, r, k - x);
32}
33
34int main(){
35//    Fastin;
36    int n, m; scanf("%d%d", &n, &m);
37    for(int i = 1; i <= n; i++){
38        scanf("%d", a + i);
39        c[i] = a[i];
40    }
41    sort(c + 1, c + 1 + n);
42    int N = (int)(unique(c + 1, c + 1 + n) - (c + 1));
43    for(int i = 1; i <= N; i++) mp[c[i]] = i;
44    
45    root[0] = build(1, N);
46    for(int i = 1; i <= n; i++)
47        root[i] = update(root[i - 1], 1, N, mp[a[i]]);
48    for(int i = 0; i < m; i++){
49        int l, r, k; scanf("%d %d %d", &l, &r, &k);
50        printf("%d\n", c[query(root[l - 1], root[r], 1, N, k)]);
51    }
52    return 0;
53}

  1const int maxn = 6e4 + 10;
  2
  3int n, m, N;
  4int a[maxn], b[maxn];
  5struct NODE{int type, x, y, z;};
  6NODE node[maxn];
  7
  8int hsh(int x){return (int)(lower_bound(b + 1, b + N, x) - b);}
  9
 10int s[maxn], rt[maxn], ls[maxn << 5], rs[maxn << 5], st[maxn << 5], top = 0;
 11
 12int build(int l, int r){
 13    int now = top++, mid = (l + r) >> 1;
 14    if(l == r) return now;
 15    ls[now] = build(l, mid);
 16    rs[now] = build(mid + 1, r);
 17    return now;
 18}
 19
 20//旧版本的节点标号为p，拥有区间[l, r]；现要在k位置加入x，返回新节点的标号
 21int update(int p, int l, int r, int k, int x){
 22    int now = top++;
 23    ls[now] = ls[p]; rs[now] = rs[p]; st[now] = st[p] + x;
 24    if(l == r) return now;
 25    
 26    int mid = (l + r) >> 1;
 27    if(k <= mid) ls[now] = update(ls[p], l, mid, k, x);
 28    else rs[now] = update(rs[p], mid + 1, r, k, x);
 29    return now;
 30}
 31
 32int use[maxn];
 33int sum(int x){
 34    int res = 0;
 35    while(x){
 36        res += st[ls[use[x]]];
 37        x -= lowbit(x);
 38    }
 39    return res;
 40}
 41
 42//当前在线段树的[l, r]位置上，左、右根节点分别为r1、r2，查询下标在(L, R]第k小的数字
 43int query(int l, int r, int r1, int r2, int L, int R, int k){
 44    if(l == r) return l;
 45    
 46    int mid = (l + r) >> 1;
 47    int res = sum(R) - sum(L) + st[ls[r2]] - st[ls[r1]];
 48    if(k <= res){
 49        for(int i = L; i; i -= lowbit(i)) use[i] = ls[use[i]];
 50        for(int i = R; i; i -= lowbit(i)) use[i] = ls[use[i]];
 51        return query(l, mid, ls[r1], ls[r2], L, R, k);
 52    }
 53    else{
 54        for(int i = L; i; i -= lowbit(i)) use[i] = rs[use[i]];
 55        for(int i = R; i; i -= lowbit(i)) use[i] = rs[use[i]];
 56        return query(mid + 1, r, rs[r1], rs[r2], L, R, k - res);
 57    }
 58}
 59
 60void update(int i, int k, int x){
 61    while(i <= N){
 62        s[i] = update(s[i], 1, N, k, x);
 63        i += lowbit(i);
 64    }
 65}
 66
 67
 68int main(){
 69//    Fastin;
 70    TTT{
 71        top = 0;
 72        scanf("%d %d", &n, &m);
 73        for(int i = 1; i <= n; i++){
 74            scanf("%d", a + i);
 75            b[i] = a[i];
 76        }
 77        N = n + 1;
 78        for(int i = 0; i < m; i++){
 79            char op[2]; scanf("%s", op);
 80            int x, y, z;
 81            if(op[0] == 'Q'){
 82                scanf("%d %d %d", &x, &y, &z);
 83                node[i] = {0, x, y, z};
 84            }
 85            else{
 86                scanf("%d %d", &x, &y);
 87                node[i] = {1, x, y};
 88                b[N++] = y;
 89            }
 90        }
 91        sort(b + 1, b + N);
 92        N = (int)(unique(b + 1, b + N) - (b + 1));
 93        
 94        
 95        rt[0] = build(1, N);
 96        for(int i = 1; i <= n; i++){
 97            rt[i] = update(rt[i - 1], 1, N, hsh(a[i]), 1);
 98            s[i] = 0;
 99        }
100        
101        for(int i = 0; i < m; i++){
102            //修改node[i].x位置的值为node[i].y;
103            if(node[i].type){
104                update(node[i].x, hsh(a[node[i].x]), -1);
105                update(node[i].x, hsh(node[i].y), 1);
106                a[node[i].x] = node[i].y;
107            }
108            //查询[node[i].x, node[i].y]中第k小的值
109            else{
110                int l = node[i].x - 1, r = node[i].y;
111                for(int i = l; i; i -= lowbit(i)) use[i] = s[i];
112                for(int i = r; i; i -= lowbit(i)) use[i] = s[i];
113                printf("%d\n", b[query(1, N, rt[l], rt[r], l, r, node[i].z)]);
114            }
115        }
116    }
117    return 0;
118}

 1const int maxn = 5e5 + 10;
 2
 3int n, q, rot;
 4struct star{int from, to, next;};
 5int head[manx];
 6star edge[maxn << 1]; int top = 0;
 7void add(itn u, int v){
 8    edge[top].from = u;
 9    edge[top].to = v;
10    edge[top].next = head[u];
11    head[u] = top++;
12}
13
14//默认标号从1开始，给重儿子打上标记。
15int son[maxn], par[maxn], sze[maxn], dep[maxn];
16void tag(int now){
17    sze[now] = 1;
18    for(int i = head[now]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(to == par[now]) continue;
20
21        par[to] = now; dep[to] = dep[now] + 1;
22        tag(to); 
23        sze[now] += sze[to];
24        if(sze[to] > sze[son[now]]) son[now] = to;
25    }
26}
27
28//将该重链的起点作为dsu中一个联通块的根节点
29int tp[maxn];
30void build(int now, int t){
31    //存在儿子，即非叶子
32    tp[now] = t;
33    if(son[now]) build(son[now], t);
34    for(int i = head[now]; ~i; i = edge[i].next){
35        int to = edge[i].to; if(to == par[now] || to == son[now]) continue;
36        build(to, to);
37    }
38}
39
40
41int lca(int u, int v){
42    while(tp[u] != tp[v]){
43        if(dep[tp[u]] > dep[tp[v]]) u = par[tp[u]];
44        else v = par[tp[v]];
45    }
46    return dep[u] < dep[v]? u: v;
47}
48
49int main(){
50    // Fastin;
51
52    clr(head, -1);
53    scanf("%d %d %d", &n, &q, &rot);
54    for(int i = 0; i < n - 1; i++){
55        int u, v; scanf("%d %d", &u, &v);
56        add(u, v); add(v, u);
57    }
58    tag(rot); build(rot, rot);
59    
60    for(int i = 0; i < q; i++){
61        int u, v; scanf("%d %d", &u, &v);
62        printf("%d\n", lca(u, v));
63    }
64}