目录

一 树上差分：

二 tarjan算法求割边

三 tarjan求割点

四  康托展开    

五 后缀数组模板：

六 后缀自动机模板：

七 求最大子矩阵

八 异或空间，线性基

九 极大团（回溯法 剪枝）

十 斯坦纳树 求给定点的最小联通代价

十一 FFT(多项式乘法)

十二 NTT

十三 回文树（统计回文串的数量）

十四 广义后缀自动机

十五 欧拉回路

十六 有向图的强联通分量以及缩点

十七 支配树（Lenguar_Tarjan算法）

十八 大数加减法

十九 树分治模版

二十 费用流

---

一 树上差分：

        对于数组来说如果我们要在区间[L,R]上增加k，那么可以在L位置上增加K，R+1位置上减小K。

       那么对于一颗数来说，如果我们要记录（x，y）之间的信息，那么可以在x和y位置+k，lca(x,y)位置减去2*k，访问的时候从叶子节点回溯到跟即是所求的值。题目：https://www.acwing.com/problem/content/description/354/

二 tarjan算法求割边

    割边判定法则：无向变（ x，y）是桥，当且仅当搜索树上存在x的一个子节点y，满足：

                                         dfn[x]<low[y]

#include<bits/stdc++.h>
using namespace std;

const int N = 1000 + 10;
int head[N], nextt[N * 2], to[N * 2], cnt = 2;
int n, m,tot=1;
int dfn[N], low[N];
bool bridge[N * 2];

void add(int u, int v) {
	to[cnt] = v, nextt[cnt] = head[u], head[u] = cnt++;
}

void tarjan(int rt, int edge) {
	dfn[rt] = low[rt] = tot++;
	for (int i = head[rt]; i; i = nextt[i]) {
		int v = to[i];
		if (!dfn[v]) {
			tarjan(v,i);
			low[rt] = min(low[rt],low[v]);
			if (dfn[rt] < low[v])bridge[i] = true;
		}
		else if (edge != (i ^ 1))low[rt] = min(low[rt],dfn[v]);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		add(u, v); add(v, u);
	}

	for (int i = 1; i <= n; i++) {
		if (!dfn[i])tarjan(i, 0);
	}

	for (int i = 2; i < cnt; i++) {
		if (bridge[i])cout << to[i] << " "<<to[i ^ 1] << endl;
	}

	return 0;
}

• 三 tarjan求割点

             判定法则：若x不是搜索树的根节点，则x是割点当且仅当搜索树上存在x的一个子节点y，满足：

                     dfn[x]<=low[y]

         特别地，若x是搜索树的根节点，则x是割点当且仅当搜索树上至少存在两个子节点y1，y2，满足上述条件。

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1000*100+10;
int n,m,cnt,num,root;
int head[N],ne[N*2],to[N*2];
int dfn[N],low[N];
bool cut[N];

void add(int u,int v){
    to[cnt]=v,ne[cnt]=head[u],head[u]=cnt++;
    to[cnt]=u,ne[cnt]=head[v],head[v]=cnt++;
}

void tarjan_point(int x){
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i!=-1;i=ne[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan_point(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                flag++;
                if(x!=root||flag>1)cut[x]=true;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

int main(){

    scanf("%d %d",&n,&m);
    cnt=2;
    for(int i=1;i<=n;i++)head[i]=-1;

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v)continue;
        add(u,v);
    }

    for(int i=1;i<=n;i++)dfn[i]=low[i]=0,cut[i]=false;

    for(int i=1;i<=n;i++){
        if(!dfn[i])root=i,tarjan_point(i);
    }

    cout<<"This is all:"<<endl;
    for(int i=1;i<=n;i++)
        if(cut[i])
            printf("%d\n",i);

}

• 四  康托展开    

          把一个全排列从小到大排序，对于给定的任意一个排列我们可以求出他属于第几个排列，即是求出有多少个排列比他小。

        有关至少参看：康托展开

         以下给出用树状数组优化后的算法：

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9 + 7;
const int MAXN=1e7;
int n,m,cnt;
int f[20],dat[20],vis[20];

struct {
    int s[20];
    void init(){
        for(int i=1;i<=n;i++)s[i]=0;
    }

    int lowerbit(int x){return x&-x;}
    void add(int x,int k){while(x<=n)s[x]+=k,x+=lowerbit(x);}
    int query(int x){int ans=0;while(x)ans+=s[x],x-=lowerbit(x);return ans;}
}bit;

void init(){
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i;
    while(m){
        dat[++cnt]=m%10;
        m/=10;
    }
}

int kangtuo(){
    int ans=0;
    for(int i=cnt;i;i--){
        ans+=bit.query(dat[i]-1)*f[i-1];
        bit.add(dat[i],-1);
    }
    return ans;
}

int main(){

    scanf("%d%d",&n,&m);
    bit.init();
    for(int i=1;i<=n;i++)bit.add(i,1);
    init();

    int n=kangtuo();
    printf("%d\n",n+1);

    return 0;
}

  康托展开的逆运算：

            就是求解第n个排列具体是什么

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9 + 7;
const int MAXN=1e7;
int n,m,cnt;
int f[20],dat[20],vis[20];

void init(){
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i;
}

int kangtuo_inver(int x){
    int num;
    int a[20];
    for(int i=1;i<=n;i++)a[i]=i;
    for(int i=1;i<=n;i++){
        num=x/f[n-i];
        x=x%f[n-i];
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(cnt==num&&a[j]<n+1){
                dat[i]=a[j];
                a[j]=n+1;
                break;
            }
            if(a[j]<n+1)cnt++;
        }
    }
}

int main(){

    scanf("%d%d",&n,&m);

    init();

    kangtuo_inver(m);
    for(int i=1;i<=n;i++)printf("%d",dat[i]);

    return 0;
}

 

五 后缀数组模板：

            

#include<bits/stdc++.h>
using namespace std;

const int N =1e6 + 10;
int M;
char s[N];
int n,m;
int rak[N],h[N],tax[N],tp[N],sa[N];

void qsort(){
    for(int i=0;i<M;i++)tax[i]=0;
    for(int i=1;i<=n;i++)tax[rak[i]]++;
    for(int i=1;i<=M;i++)tax[i]+=tax[i-1];
    for(int i=N;i>=1;i--)sa[tax[rak[tp[i]]]--]=tp[i];
}

void get_sa(){
    M=130;
    for(int i=1;i<=n;i++)rak[i]=s[i]-'0'+1,tp[i]=i;
    qsort();
    for(int w=1,p=0;p<=n;w<<=1,M=p){
        p=0;
        for(int i=1;i<=w;i++)tp[++p]=n-w+i;
        for(int i=1;i<=n;i++)if(sa[i]>w)tp[++p]=sa[i]-w;
        qsort();
        
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for(int i=2;i<=n;i++){
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
        }
        
        if(p>=n)break;
    }
}


void get_h(){
    int j,k=0;
    for(int i=1;i<=n;i++){
        if(k)k--;
        int j=sa[rak[i]-1];
        while(s[i+k]==s[j+k])k++;
        h[rak[i]]=k;
    }
}


int main(){
    scanf("%s",s+1);    
    n=strlen(s+1);
    get_sa();
    get_h();
    
    for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
    cout<<endl;
    
    return 0;
}

六 后缀自动机模板：

const int N = 1000*100+10;
int sz,last;
struct state{
    int len,link;
    map<char,int>next;
}st[N*2];

void init(){
    st[0].len=0;
    st[0].link=-1;
    sz++;
    last=0;
}

void sa_extend(char c){
    int cur=sz++;
    st[cur].len=st[last].len+1;
    int p=last;
    while(p!=-1&&!st[p].next.count(c)){
        st[p].next[c]=cur;
        p=st[p].link;
    }
    if(p==-1)st[cur].link=0;
    else{
        int q=st[p].next[c];
        if(st[p].len+1==st[q].len)st[cur].link=q;
        else{
            int clone=sz++;
            st[clone].len=st[p].len+1;
            st[clone].next=st[q].next;
            st[clone].link=st[q].link;
            while(p!=-1&&st[p].next[c]==q){
                st[p].next[c]=clone;
                p=st[p].link;
            }
            st[q].link=st[cur].link=clone;
        }
    }
    last=cur;
}

七 求最大子矩阵

#include<bits/stdc++.h>
using namespace std;

const int N = 1000+10;
char s[N][N+10];
int mx1=0,mx2=0;
int a[N][N],h[N];
int L[2][N],R[2][N],up[2][N];
int n,m;

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

    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=s[i][j]-'0';
        }
    }

    int k=0;
   for(int i=1;i<=n;i++){
        k^=1;
        int lo=0,ro=m+1;
        for(int j=1;j<=m;j++){
            if(a[i][j]==0)up[k][j]=L[k][j]=0,lo=j;
            else {
                up[k][j]=i==1?1:up[k^1][j]+1;
                L[k][j]=i==1?lo+1:max(L[k^1][j],lo+1);
            }
        }
        
        for(int j=m;j;j--){
            if(a[i][j]==0)R[k][j]=m+1,ro=j;
            else{
                R[k][j]=i==1?ro-1:min(R[k^1][j],ro-1);
                int len=R[k][j]-L[k][j]+1;
                int height=up[k][j];
                ans=max(ans,heiht*len);
            }
        }
   }

    printf("%d\n",ans);
    return 0;
}

八 异或空间，线性基

        变量名不能和关键字相同

struct Line_base{
    ll b[64];
    int cnt;        //维数
    bool flag;         //能否被0表示

    void init(){
        cnt=0;
        flag=false;
        memset(b,0,sizeof(b));
    }

    void Copy(Line_base B){                 
        cnt=B.cnt;
        flag=B.flag;
        memcpy(b,B.b,sizeof(b));
    }

    void Insert(ll x){              
        for(int i=63;i>=0;i--){
            if(x&(1LL<<i))
                if(b[i])x^=b[i];
                else{
                    b[i]=x;
                    cnt++;
                    return;
                }
        }
        flag=true;
    }

    bool check(ll x){               //检查x是否能被已存在的基表示
        for(int i=63;i>=0;i--){
            if(x&(1LL<<i))
                if(b[i])x^=b[i];
            else return false;
        }
        return true;
    }

}B1,B2,B3;

高斯消元求法（基是对角矩阵）

void cal() {
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k) if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; ++k) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
}

九 极大团（回溯法 剪枝）

#include<iostream>
#include<cstring>
#include<algorithm> 
#define maxn 55
using namespace std;
int A[maxn][maxn],V[maxn];
int cn,bestn;  //当前节点数，最大节点数
int n;
int check(int x){
    for (int i=1;i<x;i++){
        if (V[i] && !A[x][i]) return 0;
    }
    return 1;
}
void dfs(int x){
    if (x>n){  //此处记录最大团 
        bestn=max(cn,bestn);
        return ;
    }
    if (check(x)){
        cn++;
        V[x]=1;
        dfs(x+1);
        cn--;
    }
    if (cn+n-x>bestn){
        V[x]=0;
        dfs(x+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while (cin >> n && n){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++) cin >> A[i][j];
        }
        cn=bestn=0;
        memset(V,0,sizeof(V));
        dfs(1);
        cout << bestn << endl;
    }
    return 0;
}

十 斯坦纳树 求给定点的最小联通代价

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <map>
typedef long long int ll;
const int MOD = (int)1e9 + 7;
const int INF = 99999999;
using namespace std;

int n, m;
map<string, int> city;
int dp1[1 << 8][35];
int dp2[1 << 8];
int d[35][35];
int vis[35];

bool check(int s)
{
    for (int i = 0; i < 4; i++)
    {
        if (((s & 3) != 3) && ((s & 3) != 0))
            return false;

        s >>= 2;
    }

    return true;
}

int main()
{
    while (~scanf("%d%d", &n, &m) && (n || m))
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = (i == j) ? 0 : INF;

        string s1, s2;
        int w;
        for (int i = 0; i < n; i++)
        {
            cin >> s1;
            city[s1] = i;
        }
        for (int i = 0; i < m; i++)
        {
            cin >> s1 >> s2 >> w;
            int u = city[s1];
            int v = city[s2];

            if (w < d[u][v])
                d[u][v] = d[v][u] = w;
        }

        // Floyd
        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 < 8; i++)
        {
            cin >> s1;

            for (int j = 0; j < n; j++)
                dp1[1 << i][j] = d[j][city[s1]];
        }

        for (int i = 0; i < (1 << 8); i++)
        {
            if (!(i & (i - 1)))
                continue;

            for (int j = 0; j < n; j++)
            {
                dp1[i][j] = INF;

                for (int sub = (i - 1) & i; sub != 0; sub = (sub - 1) & i)
                    dp1[i][j] = min(dp1[i][j], dp1[sub][j] + dp1[i - sub][j]);
            }

            memset(vis, 0, sizeof(vis));

            int min_w, min_i;
            for (int j = 0; j < n; j++)
            {
                min_w = INF;

                for (int k = 0; k < n; k++)
                {
                    if (dp1[i][k] < min_w && !vis[k])
                    {
                        min_w = dp1[i][k];
                        min_i = k;
                    }
                }

                vis[min_i] = 1;

                for (int k = 0; k < n; k++)
                    dp1[i][min_i] = min(dp1[i][min_i], dp1[i][k] + d[k][min_i]);
            }
        }

        for (int i = 0; i < (1 << 8); i++)
        {
            dp2[i] = INF;

            for (int j = 0; j < n; j++)
                dp2[i] = min(dp2[i], dp1[i][j]);
        }

        for (int i = 0; i < (1 << 8); i++)
        {
            if (check(i))
            {
                for (int j = i; j != 0; j = (j - 1) & i)
                {
                    if (check(j))
                        dp2[i] = min(dp2[i], dp2[j] + dp2[i - j]);
                }
            }
        }

        printf("%d\n", dp2[(1 << 8) - 1]);
    }
    return 0;
}

十一 FFT(多项式乘法)

#include<bits/stdc++.h>
using namespace std;

#define PI acos(-1.0)
const int N =1000*10000+10;
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
    Complex operator + (Complex a){return Complex(x+a.x,y+a.y);}
    Complex operator - (Complex a){return Complex(x-a.x,y-a.y);}
    Complex operator * (Complex a){return Complex(x*a.x-y*a.y,x*a.y+a.x*y);}

}a[N],b[N];
int n,m,limit=1,l=0,r[N];

void FFT(Complex *A,int type){
    for(int i=0;i<limit;i++)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int mid=1;mid<limit;mid<<=1){
        Complex wn(cos(PI/mid),type*sin(PI/mid));
        for(int R=mid<<1,j=0;j<limit;j+=R){
            Complex w(1,0);
            for(int k=0;k<mid;k++,w=w*wn){
                Complex x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}

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

    for(int i=0;i<=n;i++)scanf("%lf",&a[i].x);
    for(int i=0;i<=m;i++)scanf("%lf",&b[i].x);

    while(limit<=n+m)limit<<=1,l++;

    for(int i=0;i<limit;i++){
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    
    FFT(a,1);
    FFT(b,1);

    for(int i=0;i<=limit;i++)a[i]=a[i]*b[i];
    FFT(a,-1);

    for(int i=0;i<=n+m;i++){
        printf("%d ",(int)(a[i].x/limit+0.5));
    }

    return 0;
}

十二 NTT

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 10 * 1e6 + 10, P = 998244353, G = 3, Gi = 332748118;
char buf[1<<21], *p1 = buf, *p2 = buf;


int N, M, limit = 1, L, r[MAXN];
ll a[MAXN], b[MAXN];

inline ll fastpow(ll a, ll k) {
    ll base = 1;
    while(k) {
        if(k & 1) base = (base * a ) % P;
        a = (a * a) % P;
        k >>= 1;
    }
    return base % P;
}

inline void NTT(ll *A, int type) {
    for(int i = 0; i < limit; i++)
        if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid <<= 1) {
        ll Wn = fastpow( type == 1 ? G : Gi , (P - 1) / (mid << 1));
        for(int j = 0; j < limit; j += (mid << 1)) {
            ll w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P) {
                 int x = A[j + k], y = w * A[j + k + mid] % P;
                 A[j + k] = (x + y) % P,
                 A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
}

int main() {

    scanf("%d%d",&N,&M);

    for(int i = 0; i <= N; i++) scanf("%lld",a+i),a[i] = (a[i] + P) % P;
    for(int i = 0; i <= M; i++) scanf("%lld",b+i),b[i] = (b[i] + P) % P;

    while(limit <= N + M) limit <<= 1, L++;
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));

    NTT(a, 1);
    NTT(b, 1);

    for(int i = 0; i < limit; i++) a[i] = (a[i] * b[i]) % P;
    NTT(a, -1);
    ll inv = fastpow(limit, P - 2);

    for(int i = 0; i <= N + M; i++)
        printf("%lld ", (a[i] * inv) % P);

    return 0;
}

十三 回文树（统计回文串的数量）

struct Palindromic_Tree {
	int next[MAXN][26];
	int fail[MAXN];
	int cnt[MAXN];
	int num[MAXN];
	int len[MAXN];
	int S[MAXN];
	int last;
	int n;
	int p;

	int newnode(int l)
	{
		for (int i = 0; i < 26; ++i) next[p][i] = 0;
		cnt[p] = 0;
		num[p] = 0;
		len[p] = l;
		return p++;
	}

	void Init()
	{
		p = 0;
		newnode(0);
		newnode(-1);
		last = 0;
		n = 0;
		S[n] = -1;
		fail[0] = 1;
	}

	int get_fail(int x)
	{
		while (S[n - len[x] - 1] != S[n])x = fail[x];
		return x;
	}

	void add(int c)
	{
		S[++n] = c;
		int cur = get_fail(last);
		if (!next[cur][c])
		{
			int now = newnode(len[cur] + 2);
			fail[now] = next[get_fail(fail[cur])][c];
			next[cur][c] = now;
			num[now] = num[fail[now]] + 1;
		}
		last = next[cur][c];
		cnt[last]++;
	}

	ll count()
	{
		ll res = p * 1ll;
		for (int i = p - 1; i >= 0; --i) cnt[fail[i]] += cnt[i];
		return (res - 2);//本质不同的回文串数量 
	}
}pam;

十四 广义后缀自动机

struct SAM {
	/*sam.init();      空间要开四倍
	ll c = 0;     不同子串的数量
	for (int i = 0; i < len; ++i) {
		sam.extend(s[i] - 'a');
		c += i + 1LL - sam.len[sam.fa[sam.last]];
	}*/
	static const int M = MAXN << 2;
	int nxt[M][27], len[M] = { -1 }, fa[M], sz = 2, last = 1;
	int newnode() {
		memset(nxt[sz], 0, sizeof nxt[sz]);
		len[sz] = len[last] + 1;
		return last = sz++;
	}
	void init() {
		sz = 2, last = 1;
		memset(nxt[1], 0, sizeof nxt[1]);
	}
	void extend(int ch) {
		int p = last, np = newnode();
		for (; p && !nxt[p][ch]; p = fa[p]) nxt[p][ch] = np;

		if (!p) {
			fa[np] = 1;
			return;
		}

		int q = nxt[p][ch];

		if (len[p] + 1 == len[q]) fa[np] = q;
		else {
			int nq = sz++;
			len[nq] = len[p] + 1;
			memcpy(nxt[nq], nxt[q], sizeof nxt[0]);

			fa[nq] = fa[q];
			fa[np] = fa[q] = nq;
			for (; nxt[p][ch] == q; p = fa[p]) nxt[p][ch] = nq;
		}
	}

} sam;

十五 欧拉回路

#include<bits/stdc++.h>
using namespace std;
const int N = 10000+10,M = 40000+10;
int n,m;
int head[N],nextt[M*2],to[M*2],cnt=1;
int sk[N*100],ans[N*100];
int top,t;
bool vis[N*100];

void add(int u,int v){
    to[cnt]=v,nextt[cnt]=head[u],head[u]=cnt++;
}
void euler(){
    sk[++top]=1;
    while(top>0){
        int x=sk[top],i=head[x];
        while(i&&(vis[i]))i=nextt[i];
        if(i){
            sk[++top]=to[i];
            vis[i]=vis[i^1]=true;
            head[x]=nextt[i];
        }
        else {
            top--;
            ans[++t]=x;
        }
    }
        
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v; scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    euler();
    for(int i=t;i;i--)printf("%d\n",ans[i]);
    return 0;
}

十六 有向图的强联通分量以及缩点

/*
    cnt: 强联通分量的数目
    c[x]:x点属于的强联通分量的的编号
    scc[x]:编号为x的强联通分量中的点
*/
#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int n;
int head[N],nextt[N],to[N];
int hd[N],ne[N],To[N];
int dfn[N],low[N];
int num,top,tot,cnt,tc;
int s[N],ins[N],c[N];
int in[N],out[N];
vector<int>scc[N];

void add(int u,int v){
    to[++tot]=v,nextt[tot]=head[u],head[u]=tot;
}

void add_c(int u,int v){
    To[++tc]=v,ne[tc]=hd[u],hd[u]=tc;
}

void tarjan(int x){
    dfn[x]=low[x]=++num;
    s[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=nextt[i]){
        if(!dfn[to[i]]){
            tarjan(to[i]);
            low[x]=min(low[x],low[to[i]]);
        }
        else if(ins[to[i]])low[x]=min(low[x],dfn[to[i]]);
    }
    if(dfn[x]==low[x]){
        cnt++; int y;
        do{
            y=s[top--],ins[y]=0;
            c[y]=cnt,scc[cnt].push_back(y);
        }while(x!=y);
    }
    
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        while(scanf("%d",&x),x){
            add(i,x);
        }
    }
    
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    } 
                                //缩点
   for(int x=1;x<=n;x++){
       for(int i=head[x];i;i=nextt[i]){
           int y=to[i];
           if(c[x]==c[y])continue;
           add_c(c[x],c[y]);
       }
   }

    
    
    return 0;
}

十七 支配树（Lenguar_Tarjan算法）

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3e5+10;
int n,m,dfs_clock,dfn[N],rev[N],f[N];  //点的dfs序，dfs对应的点，父亲结点 
int semi[N],idom[N],Ans[N];  //半支配点，支配点，答案

struct Node{int to,next;};
struct Graph{  //树 
  int tot,head[N];
  Node E[N]; 
  inline void clear() {
    tot=0;
    for(int i=0;i<=n;++i) head[i]=0;
  }
  inline void link(int u,int v) {
    E[++tot]=(Node){v,head[u]}; head[u]=tot;
  }
}pre,nxt,dom;  //nxt原树，pre反树，dom支配树 

struct uset{  //并查集 
  int fa[N],Mi[N];
  inline void init() {
    for(int i=1;i<=n;++i)
      fa[i]=Mi[i]=semi[i]=i;
  }
  inline int find(int x){
    if(fa[x]==x)return x;
    int fx=fa[x],y=find(fa[x]);
    if(dfn[semi[Mi[fx]]]<dfn[semi[Mi[x]]])Mi[x]=Mi[fx];
    return fa[x]=y;
  }
}uset;

inline void dfs(int x) {  //先dfs一遍计算dfn,rev,father数组 
  dfn[x]=++dfs_clock;rev[dfs_clock]=x;
  for(int e=nxt.head[x];e;e=nxt.E[e].next){
    if(!dfn[nxt.E[e].to])
      f[nxt.E[e].to]=x,dfs(nxt.E[e].to);
  }
}

inline void getans(int x) {  //计算答案，每个点被多少个点支配 
  Ans[x]=1;
  for(int e=dom.head[x];e;e=dom.E[e].next) {
      getans(dom.E[e].to);
      Ans[x]+=Ans[dom.E[e].to];
  } 
}

inline void calc() {  //构建支配树 
  for(int i=n;i>=2;--i) {  //从dfs序大的点开始 
    int y=rev[i],tmp=n;
    for(int e=pre.head[y];e;e=pre.E[e].next) {  //所有能到达y点的边 
      int x=pre.E[e].to;  // (x,y) 
      if (!dfn[x]) continue;
      if (dfn[x]<dfn[y]) tmp=min(tmp,dfn[x]);
      else uset.find(x),tmp=min(tmp,dfn[semi[uset.Mi[x]]]);
    }
    semi[y]=rev[tmp];uset.fa[y]=f[y];
    dom.link(semi[y],y);
    
    y=rev[i-1];
    for (int e=dom.head[y];e;e=dom.E[e].next) {
      int x=dom.E[e].to; uset.find(x);
      if (semi[uset.Mi[x]]==y) idom[x]=y;
      else idom[x]=uset.Mi[x];
    }
  }

  for(int i=2;i<=n;++i){
    int x=rev[i];
    if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
  }
  
  dom.clear();
  for(int i=2;i<=n;++i) dom.link(idom[i],i);  //2-n点连接支配树 
    
  getans(1);  //计算答案 
  for(int i=1;i<=n;++i) {
    printf("%d",Ans[i]),Ans[i]=0;
    i==n?printf("\n"):printf(" ");
  }
}

//P5180支配树模板  起点为1的有向图  求每个点能支配的点的个数（包括自己）
int main() {
  scanf("%d%d",&n,&m);
      dfs_clock=0; pre.clear(); nxt.clear(); dom.clear();
      for(int i=1;i<=n;++i) dfn[i]=rev[i]=semi[i]=idom[i]=f[i]=0;
    for(int i=1;i<=m;++i) {
      int u,v; scanf("%d%d",&u,&v);
      nxt.link(u,v);
      pre.link(v,u);
    }
    dfs(1);
    uset.init();
    calc();
  return 0;
}

十八 大数加减法

string add(string s1,string s2) {
	int len1 = s1.size(), len2 = s2.size();
	if (len1 < len2)swap(s1,s2);
	reverse(s1.begin(),s1.end());
	reverse(s2.begin(),s2.end());
	int len = max(len1,len2);
	string ans;
	ans.resize(len);
	int sum = 0;
	for (int i = 0; i < min(len1, len2); i++) {
		int k = sum + (s1[i] - '0') + (s2[i] - '0');
		ans[i] = k % 10+'0';
		sum = k / 10;
	}
	for (int i = min(len1, len2); i < len; i++) {
		int k = sum + (s1[i] - '0');
		ans[i] = k % 10 + '0';
		sum = k / 10;
	}
	if (sum)ans.insert(ans.begin(),'0'+sum);
	reverse(ans.begin(),ans.end());
	return ans;
}

string reduce(string s1, string s2) {	//保证s1>=s2;
	int len1 = s1.size(),len2=s2.size();
	reverse(s1.begin(), s1.end()); reverse(s2.begin(),s2.end());
	string ans; ans.resize(len1);
	int re = 0;
	for (int i = 0; i < len2; i++) {
		int a = s1[i] - '0',b=s2[i]-'0';
		a -= re;
		re = 0;
		if (a < b) {
			a += 10; re++;
		}
		ans[i] = a - b + '0';
	}
	for (int i = len2; i < len1; i++) {
		int a = s1[i] - '0';
		a -= re;
		re = 0;
		if (a < 0) {
			a += 10;
			re++;
		}
		ans[i] = a + '0';
	}
	
	for (int i = len1 - 1; i >= 0; i--) {
		if (ans[i] != '0')break;
		ans.erase(ans.end()-1);
	}
	reverse(ans.begin(), ans.end());
	if (ans.size() == 0)ans.insert(ans.begin(),'0');
	return ans;
}

十九 树分治模版

牛客国庆训练一

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 200 * 100 + 10;
const int M = 400 * 100 + 10;
int n;
int sz, mx, rt,ans;
int head[N], to[M], len[M], ne[M], cnt;
int dis[N], siz[N],vis[N],num[2020];

void add(int x, int y, int w) {
	to[++cnt] = y, len[cnt] = w, ne[cnt] = head[x], head[x] = cnt;
}

int getrt(int x, int f) {
	siz[x] = 1;
	int ans = 0;
	for (int i = head[x],y; i; i = ne[i]) {
		y = to[i];
		if (y == f || vis[y])continue;
		siz[x] += getrt(y,x);
		ans = max(ans,siz[y]);
	}
	ans = max(ans,sz-siz[x]);
	if (ans < mx) {
		mx = ans;
		rt = x;
	}
	return siz[x];
}

void getdis(int x, int f) {
	num[dis[x] % 2019]++;
	for (int i = head[x],y; i; i = ne[i]) {
		y = to[i];
		if (y == f || vis[y])continue;
		dis[y] = (dis[x] + len[i]) % 2019;
		getdis(y,x);
	}
}

int solve(int x, int ds) {
	memset(num, 0, sizeof(num));
	dis[x] = ds % 2019;
	getdis(x,0);
	int ans = num[0] * (num[0] - 1) / 2;
	for (int i = 1; i <= 2019 / 2; i++) {
		ans += num[i] * num[2019 - i];
	}
	return ans;
}

void dfs(int x) {
	ans += solve(x,0);
	vis[x] = 1;
	for (int i = head[x],y; i; i = ne[i]) {
		y = to[i];
		if (vis[y])continue;
		ans -= solve(y, len[i]);
		mx = INF;
		sz = siz[y];
		getrt(y,0);
		dfs(rt);
	}
}

int main() {
	while (scanf("%d", &n) == 1) {
		for (int i = 1; i <= n; i++)head[i] = dis[i] = vis[i] = 0;
		ans = 0; cnt = 1;
		for (int i = 1, x, y, w; i < n; i++) {
			scanf("%d%d%d",&x,&y,&w);
			add(x, y, w); add(y, x, w);
		}
		sz = n; mx = INF;
		getrt(1,0);
		dfs(rt);
		printf("%d\n",ans);
	}
	return 0;
}

二十 费用流

#include<bits/stdc++.h>
using namespace std;
const int N = 5010, M = 100000+10;
int ver[M], edge[M], cost[M], ne[M], head[N];
int d[N], incf[N], pre[N], v[N];
int n, k, m,tot, s, t, maxflow, ans;

void add(int x, int y, int z, int c) {
	ver[++tot] = y, edge[tot] = z, cost[tot] = c, ne[tot] = head[x], head[x] = tot;
	ver[++tot] = x, edge[tot] = 0, cost[tot] = -c, ne[tot] = head[y], head[y] = tot;
}

int num(int i, int j, int k) {
	return (i - 1)*n + j + k * n*n;
}

//最小费用跑最短路，最大费用跑最长路；
bool spfa() {
	queue<int>q;
	memset(d, 0x3f, sizeof(d));
	//memset(d, 0xcf, sizeof(d)); 负无穷

	memset(v, 0, sizeof(v));
	q.push(s); d[s] = 0, v[s] = 1;
	incf[s] = 1 << 30;
	while (q.size()) {
		int x = q.front(); v[x] = 0; q.pop();
		for (int i = head[x]; i; i = ne[i]) {
			if (!edge[i])continue;
			int y = ver[i];
			if (d[y] > d[x] + cost[i]) {
				d[y] = d[x] + cost[i];
				incf[y] = min(incf[x], edge[i]);
				pre[y] = i;
				if (!v[y])v[y] = 1, q.push(y);
			}
		}
	}
	if (d[t] == 0x3f3f3f3f)return false;
	return true;
}

void update() {
	int x = t;
	while (x != s) {
		int i = pre[x];
		edge[i] -= incf[t];
		ans += incf[t] * cost[i];
		edge[i ^ 1] += incf[t];
		x = ver[i ^ 1];
	}
	maxflow += incf[t];
}

int main() {
	cin >> n >> m >> s >> t;
	tot = 1;
	for (int i = 1; i <= m; i++) {
		int x, y, c, w;
		scanf("%d%d%d%d",&x,&y,&c,&w);
		add(x,y,c,w);
	}
	while (spfa())update();
	cout <<maxflow<<" "<< ans << endl;
	return 0;
}