NOI模板复习组——图论部分

1.最小生成树：

kruscal:

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[400005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[400005];

int f[200005];

int head[200005];

int cnt=1;

int n,m;

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

int main()

{

    read(n),read(m);

    init();

    for(int i=1;i<=m;i++)read(e[i].l),read(e[i].r),read(e[i].v);

    kruscal();

    return 0;

}

2.最短路：

spfa（最好不要写，他死了）...

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[1000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[500005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[200005];

int head[200005];

ll dis[200005];

bool used[200005];

int cnt=1;

int n,m,S,T;

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

int main()

{

    read(n),read(m),read(S);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y),read(z);

        add(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    //kruscal();

    spfa(S);

    //diji(S);

    return 0;

}

dijisktra（这个比较好）

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[1000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[500005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[200005];

int head[200005];

ll dis[200005];

bool used[200005];

int cnt=1;

int n,m,S,T;

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

int main()

{

    read(n),read(m),read(S);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y),read(z);

        add(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    //kruscal();

    //spfa(S);

    diji(S);

    return 0;

}

3.LCA

倍增版本：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

int fa[500005][25];

int dep[500005];

int siz[500005],son[500005],ttop[500005];

bool used[500005];

int cnt=1;

int n,m,S,T;

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

int main()

{

    read(n),read(m),read(S);

    init();

    for(int i=1;i<n;i++)

    {

        int x,y;ll z;

        read(x),read(y);//,read(z);

        add(x,y,z),add(y,x,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    //kruscal();

    //spfa(S);

    //diji(S);

    tree_dfs(S,S);//,tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",quick_jump_LCA(x,y));

    }

    return 0;

}

树剖版本：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

int fa[500005][25];

int dep[500005];

int siz[500005],son[500005],ttop[500005];

bool used[500005];

int cnt=1;

int n,m,S,T;

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

int main()

{

    read(n),read(m),read(S);

    init();

    for(int i=1;i<n;i++)

    {

        int x,y;ll z;

        read(x),read(y);//,read(z);

        add(x,y,z),add(y,x,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    //kruscal();

    //spfa(S);

    //diji(S);

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

    return 0;

}

4.tarjan

有向图tarjan缩点+spfa最长路

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

ll va[500005];

int dfn[500005],low[500005],posi[500005];

ll src_num[500005],src_cnt;

int my_stack[500005],top=0;

int fa[500005][25];

int dep[500005];

int spe[500005],nu;

int siz[500005],son[500005],ttop[500005];

bool used[500005];

int cnt=1,deep;

int n,m,S,T;

vector <int> v[500005];

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]+=va[t];

            posi[t]=src_cnt;

        }

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

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

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

int main()

{

    read(n),read(m);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y);//,read(z);

        add(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    direc_tarjan();

    return 0;

}

无向图割边：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

ll va[500005];

int dfn[500005],low[500005],posi[500005];

ll src_num[500005],src_cnt;

int my_stack[500005],top=0;

int fa[500005][25];

int dep[500005];

int spe[500005],nu;

int siz[500005],son[500005],ttop[500005];

int inr[500005],our[500005];

bool used[500005];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[500005];

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]+=va[t];

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

int main()

{

    read(n),read(m);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z=i;

        read(x),read(y);//,read(z);

        add(x,y,z),add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    cut_line_tarjan();

    return 0;

}

无向图割点：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

ll va[500005];

int dfn[500005],low[500005],posi[500005];

ll src_num[500005],src_cnt;

int my_stack[500005],top=0;

int fa[500005][25];

int dep[500005];

int spe[500005],nu;

int siz[500005],son[500005],ttop[500005];

int inr[500005],our[500005];

bool used[500005];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[500005];

vector <int> peo[500005];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]+=va[t];

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int main()

{

    read(n),read(m);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z=i;

        read(x),read(y);//,read(z);

        add(x,y,z),add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    cut_point_tarjan();

    return 0;

}

5.网络流

最大流：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

    ll pri;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

ll va[500005];

int dfn[500005],low[500005],posi[500005];

ll src_num[500005],src_cnt;

int my_stack[500005],top=0;

int fa[500005][25];

int dep[500005];

int spe[500005],nu;

int siz[500005],son[500005],ttop[500005];

int inr[500005],our[500005];

int cur[500005];

ll lim[500005];

bool used[500005];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[500005];

vector <int> peo[500005];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,int w)

{

    add(l,r,w),add(r,l,0);

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]+=va[t];

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool dinic_bfs()

{

    memset(dis,0,sizeof(dis));

    memcpy(cur,head,sizeof(head));

    dis[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[T];

}

ll dinic_dfs(int x,ll lim)

{

    if(x==T)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dinic_dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp,lim-=temp;

                edge[i].val-=temp,edge[ide(i)].val+=temp;

                if(!lim)break;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(dinic_bfs())ans+=dinic_dfs(S,INF);

    return ans;

}

void max_flow()

{

    printf("%lld\n",dinic());

}

int main()

{

    read(n),read(m),read(S),read(T);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y),read(z);

        dadd(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    max_flow();

    return 0;

}

费用流：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

    ll pri;

}edge[5000005];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[5000005];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[500005];

int head[500005];

ll dis[500005];

ll va[500005];

int dfn[500005],low[500005],posi[500005];

ll src_num[500005],src_cnt;

int my_stack[500005],top=0;

int fa[500005][25];

int dep[500005];

int spe[500005],nu;

int siz[500005],son[500005],ttop[500005];

int inr[500005],our[500005];

int cur[500005];

int pre[500005];

ll lim[500005];

bool used[500005];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[500005];

vector <int> peo[500005];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,int w)

{

    add(l,r,w),add(r,l,0);

}

void cost_add(int l,int r,ll w,ll p)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    edge[cnt].pri=p;

    head[l]=cnt++;

}

void cost_dadd(int l,int r,ll w,ll p)

{

    cost_add(l,r,w,p),cost_add(r,l,0,-p);

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]+=va[t];

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool dinic_bfs()

{

    memset(dis,0,sizeof(dis));

    memcpy(cur,head,sizeof(head));

    dis[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[T];

}

ll dinic_dfs(int x,ll lim)

{

    if(x==T)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dinic_dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp,lim-=temp;

                edge[i].val-=temp,edge[ide(i)].val+=temp;

                if(!lim)break;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(dinic_bfs())ans+=dinic_dfs(S,INF);

    return ans;

}

void max_flow()

{

    printf("%lld\n",dinic());

}

bool EK_spfa()

{

    memset(pre,-1,sizeof(pre));

    memset(f,0,sizeof(f));

    memset(dis,0x3f,sizeof(dis));

    dis[S]=0,lim[S]=INF,used[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&dis[to]>dis[u]+edge[i].pri)

            {

                dis[to]=dis[u]+edge[i].pri;

                pre[to]=i,f[to]=u,lim[to]=min(lim[u],edge[i].val);

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    return pre[T]!=-1;

}

void EK()

{

    ll maxf=0,minv=0;

    while(EK_spfa())

    {

        maxf+=lim[T],minv+=dis[T]*lim[T];

        int temp=T;

        while(temp!=S)edge[pre[temp]].val-=lim[T],edge[ide(pre[temp])].val+=lim[T],temp=f[temp];

    }

    printf("%lld %lld\n",maxf,minv);

}

void min_cost_max_flow()

{

    S=1,T=n;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        cost_dadd(x,y,z,w);

    }

    EK();

}

int main()

{

    read(n),read(m);//,read(S),read(T);

    init();

    min_cost_max_flow();

    return 0;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y),read(z);

        dadd(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    max_flow();

    return 0;

}

有源汇上下界最大流

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

const int maxn=2000005;

const int maxm=5000005;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

    ll pri;

}edge[maxm];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[maxm];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[maxn];

int head[maxn];

ll dis[maxn];

ll va[maxn];

int dfn[maxn],low[maxn],posi[maxn];

ll src_num[maxn],src_cnt;

int my_stack[maxn],top=0;

int fa[maxn][25];

int dep[maxn];

int spe[maxn],nu;

int siz[maxn],son[maxn],ttop[maxn];

int inr[maxn],our[maxn];

int cur[maxn];

int pre[maxn];

ll lim[maxn];

bool used[maxn];

ll fin[maxn],fout[maxn];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[maxn];

vector <int> peo[maxn];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    //for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,ll w)

{

    add(l,r,w),add(r,l,0);

}

void cost_add(int l,int r,ll w,ll p)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    edge[cnt].pri=p;

    head[l]=cnt++;

}

void cost_dadd(int l,int r,ll w,ll p)

{

    cost_add(l,r,w,p),cost_add(r,l,0,-p);

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool dinic_bfs()

{

    memset(dis,0,sizeof(dis));

    memcpy(cur,head,sizeof(head));

    dis[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[T];

}

ll dinic_dfs(int x,ll lim)

{

    if(x==T)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dinic_dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp,lim-=temp;

                edge[i].val-=temp,edge[ide(i)].val+=temp;

                if(!lim)break;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(dinic_bfs())ans+=dinic_dfs(S,INF);

    return ans;

}

void max_flow()

{

    printf("%lld\n",dinic());

}

bool EK_spfa()

{

    memset(pre,-1,sizeof(pre));

    memset(f,0,sizeof(f));

    memset(dis,0x3f,sizeof(dis));

    dis[S]=0,lim[S]=INF,used[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&dis[to]>dis[u]+edge[i].pri)

            {

                dis[to]=dis[u]+edge[i].pri;

                pre[to]=i,f[to]=u,lim[to]=min(lim[u],edge[i].val);

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    return pre[T]!=-1;

}

void EK()

{

    ll maxf=0,minv=0;

    while(EK_spfa())

    {

        maxf+=lim[T],minv+=dis[T]*lim[T];

        int temp=T;

        while(temp!=S)edge[pre[temp]].val-=lim[T],edge[ide(pre[temp])].val+=lim[T],temp=f[temp];

    }

    printf("%lld %lld\n",maxf,minv);

}

void min_cost_max_flow()

{

    S=1,T=n;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        cost_dadd(x,y,z,w);

    }

    EK();

}

void two_SAT()

{

    for(int i=1;i<=m;i++)

    {

        int x,y,z,w;

        read(x),read(y),read(z),read(w);

        if(y==1&&w==1)add(x+n,z,0),add(z+n,x,0);

        else if(y==1)add(x+n,z+n,0),add(z,x,0);

        else if(w==1)add(x,z,0),add(z+n,x+n,0);

        else add(x,z+n,0),add(z,x+n,0);

    }

    n<<=1;

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    n>>=1;

    for(int i=1;i<=n;i++)if(posi[i]==posi[i+n]){printf("IMPOSSIBLE\n");exit(0);}

    printf("POSSIBLE\n");

    for(int i=1;i<=n;i++)

    {

        if(posi[i]<posi[i+n])printf("1 ");

        else printf("0 ");

    }

    printf("\n");

}

bool dfs(int x)

{

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(used[to])continue;

        used[to]=1;

        if(!f[to]||dfs(f[to])){f[to]=x;return 1;}

    }

    return 0;

}

int hungary()

{

    int ret=0;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n+m;j++)used[j]=0;

        if(dfs(i))ret++;

    }

    return ret;

}

void two_match()

{

    read(n),read(m),read(S);

    for(int i=1;i<=S;i++)

    {

        int x,y;

        read(x),read(y);

        if(x>n||y>m)continue;

        add(x,y+n,0),add(y+n,x,0);

    }

    printf("%d\n",hungary());

}

void upper_lower_maxflow()

{

    int temps=S,tempt=T;

    S=n+1,T=n+2;

    ll sum=0;

    for(int i=1;i<=n;i++)

    {

        if(fin[i]>fout[i])dadd(S,i,fin[i]-fout[i]),sum+=fin[i]-fout[i];

        else dadd(i,T,fout[i]-fin[i]);

    }

    if(dinic()<sum)printf("please go home to sleep\n");

    else S=temps,T=tempt,printf("%lld\n",dinic());

}

void upper_lower_minflow()

{

    int temps=S,tempt=T;

    S=n+1,T=n+2;

    ll sum=0;

    for(int i=1;i<=n;i++)

    {

        if(fin[i]>fout[i])dadd(S,i,fin[i]-fout[i]),sum+=fin[i]-fout[i];

        else dadd(i,T,fout[i]-fin[i]);

    }

    if(dinic()<sum)printf("please go home to sleep\n");

    else S=tempt,T=temps,printf("%lld\n",INF-dinic());

}

int main()

{

    read(n),read(m),read(S),read(T);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        fin[y]+=z,fout[x]+=z;

        dadd(x,y,w-z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    dadd(T,S,INF);

    upper_lower_maxflow();

    return 0;

}

有源汇上下界最小流

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

const int maxn=2000005;

const int maxm=5000005;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

    ll pri;

}edge[maxm];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[maxm];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[maxn];

int head[maxn];

ll dis[maxn];

ll va[maxn];

int dfn[maxn],low[maxn],posi[maxn];

ll src_num[maxn],src_cnt;

int my_stack[maxn],top=0;

int fa[maxn][25];

int dep[maxn];

int spe[maxn],nu;

int siz[maxn],son[maxn],ttop[maxn];

int inr[maxn],our[maxn];

int cur[maxn];

int pre[maxn];

ll lim[maxn];

bool used[maxn];

ll fin[maxn],fout[maxn];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[maxn];

vector <int> peo[maxn];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    //for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,ll w)

{

    add(l,r,w),add(r,l,0);

}

void cost_add(int l,int r,ll w,ll p)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    edge[cnt].pri=p;

    head[l]=cnt++;

}

void cost_dadd(int l,int r,ll w,ll p)

{

    cost_add(l,r,w,p),cost_add(r,l,0,-p);

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool dinic_bfs()

{

    memset(dis,0,sizeof(dis));

    memcpy(cur,head,sizeof(head));

    dis[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[T];

}

ll dinic_dfs(int x,ll lim)

{

    if(x==T)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dinic_dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp,lim-=temp;

                edge[i].val-=temp,edge[ide(i)].val+=temp;

                if(!lim)break;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(dinic_bfs())ans+=dinic_dfs(S,INF);

    return ans;

}

void max_flow()

{

    printf("%lld\n",dinic());

}

bool EK_spfa()

{

    memset(pre,-1,sizeof(pre));

    memset(f,0,sizeof(f));

    memset(dis,0x3f,sizeof(dis));

    dis[S]=0,lim[S]=INF,used[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&dis[to]>dis[u]+edge[i].pri)

            {

                dis[to]=dis[u]+edge[i].pri;

                pre[to]=i,f[to]=u,lim[to]=min(lim[u],edge[i].val);

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    return pre[T]!=-1;

}

void EK()

{

    ll maxf=0,minv=0;

    while(EK_spfa())

    {

        maxf+=lim[T],minv+=dis[T]*lim[T];

        int temp=T;

        while(temp!=S)edge[pre[temp]].val-=lim[T],edge[ide(pre[temp])].val+=lim[T],temp=f[temp];

    }

    printf("%lld %lld\n",maxf,minv);

}

void min_cost_max_flow()

{

    S=1,T=n;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        cost_dadd(x,y,z,w);

    }

    EK();

}

void two_SAT()

{

    for(int i=1;i<=m;i++)

    {

        int x,y,z,w;

        read(x),read(y),read(z),read(w);

        if(y==1&&w==1)add(x+n,z,0),add(z+n,x,0);

        else if(y==1)add(x+n,z+n,0),add(z,x,0);

        else if(w==1)add(x,z,0),add(z+n,x+n,0);

        else add(x,z+n,0),add(z,x+n,0);

    }

    n<<=1;

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    n>>=1;

    for(int i=1;i<=n;i++)if(posi[i]==posi[i+n]){printf("IMPOSSIBLE\n");exit(0);}

    printf("POSSIBLE\n");

    for(int i=1;i<=n;i++)

    {

        if(posi[i]<posi[i+n])printf("1 ");

        else printf("0 ");

    }

    printf("\n");

}

bool dfs(int x)

{

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(used[to])continue;

        used[to]=1;

        if(!f[to]||dfs(f[to])){f[to]=x;return 1;}

    }

    return 0;

}

int hungary()

{

    int ret=0;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n+m;j++)used[j]=0;

        if(dfs(i))ret++;

    }

    return ret;

}

void two_match()

{

    read(n),read(m),read(S);

    for(int i=1;i<=S;i++)

    {

        int x,y;

        read(x),read(y);

        if(x>n||y>m)continue;

        add(x,y+n,0),add(y+n,x,0);

    }

    printf("%d\n",hungary());

}

void upper_lower_maxflow()

{

    int temps=S,tempt=T;

    S=n+1,T=n+2;

    ll sum=0;

    for(int i=1;i<=n;i++)

    {

        if(fin[i]>fout[i])dadd(S,i,fin[i]-fout[i]),sum+=fin[i]-fout[i];

        else dadd(i,T,fout[i]-fin[i]);

    }

    if(dinic()<sum)printf("please go home to sleep\n");

    else S=temps,T=tempt,printf("%lld\n",dinic());

}

void upper_lower_minflow()

{

    int temps=S,tempt=T;

    S=n+1,T=n+2;

    ll sum=0;

    for(int i=1;i<=n;i++)

    {

        if(fin[i]>fout[i])dadd(S,i,fin[i]-fout[i]),sum+=fin[i]-fout[i];

        else dadd(i,T,fout[i]-fin[i]);

    }

    if(dinic()<sum)printf("please go home to sleep\n");

    else S=tempt,T=temps,printf("%lld\n",INF-dinic());

}

int main()

{

    read(n),read(m),read(S),read(T);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        fin[y]+=z,fout[x]+=z;

        dadd(x,y,w-z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    dadd(T,S,INF);

    upper_lower_minflow();

    return 0;

}

6.2-SAT

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

const int maxn=2000005;

const int maxm=5000005;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

    ll pri;

}edge[maxm];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[maxm];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[maxn];

int head[maxn];

ll dis[maxn];

ll va[maxn];

int dfn[maxn],low[maxn],posi[maxn];

ll src_num[maxn],src_cnt;

int my_stack[maxn],top=0;

int fa[maxn][25];

int dep[maxn];

int spe[maxn],nu;

int siz[maxn],son[maxn],ttop[maxn];

int inr[maxn],our[maxn];

int cur[maxn];

int pre[maxn];

ll lim[maxn];

bool used[maxn];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[maxn];

vector <int> peo[maxn];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    //for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,int w)

{

    add(l,r,w),add(r,l,0);

}

void cost_add(int l,int r,ll w,ll p)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    edge[cnt].pri=p;

    head[l]=cnt++;

}

void cost_dadd(int l,int r,ll w,ll p)

{

    cost_add(l,r,w,p),cost_add(r,l,0,-p);

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool dinic_bfs()

{

    memset(dis,0,sizeof(dis));

    memcpy(cur,head,sizeof(head));

    dis[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[T];

}

ll dinic_dfs(int x,ll lim)

{

    if(x==T)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dinic_dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp,lim-=temp;

                edge[i].val-=temp,edge[ide(i)].val+=temp;

                if(!lim)break;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(dinic_bfs())ans+=dinic_dfs(S,INF);

    return ans;

}

void max_flow()

{

    printf("%lld\n",dinic());

}

bool EK_spfa()

{

    memset(pre,-1,sizeof(pre));

    memset(f,0,sizeof(f));

    memset(dis,0x3f,sizeof(dis));

    dis[S]=0,lim[S]=INF,used[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&dis[to]>dis[u]+edge[i].pri)

            {

                dis[to]=dis[u]+edge[i].pri;

                pre[to]=i,f[to]=u,lim[to]=min(lim[u],edge[i].val);

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    return pre[T]!=-1;

}

void EK()

{

    ll maxf=0,minv=0;

    while(EK_spfa())

    {

        maxf+=lim[T],minv+=dis[T]*lim[T];

        int temp=T;

        while(temp!=S)edge[pre[temp]].val-=lim[T],edge[ide(pre[temp])].val+=lim[T],temp=f[temp];

    }

    printf("%lld %lld\n",maxf,minv);

}

void min_cost_max_flow()

{

    S=1,T=n;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        cost_dadd(x,y,z,w);

    }

    EK();

}

void two_SAT()

{

    for(int i=1;i<=m;i++)

    {

        int x,y,z,w;

        read(x),read(y),read(z),read(w);

        if(y==1&&w==1)add(x+n,z,0),add(z+n,x,0);

        else if(y==1)add(x+n,z+n,0),add(z,x,0);

        else if(w==1)add(x,z,0),add(z+n,x+n,0);

        else add(x,z+n,0),add(z,x+n,0);

    }

    n<<=1;

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    n>>=1;

    for(int i=1;i<=n;i++)if(posi[i]==posi[i+n]){printf("IMPOSSIBLE\n");exit(0);}

    printf("POSSIBLE\n");

    for(int i=1;i<=n;i++)

    {

        if(posi[i]<posi[i+n])printf("1 ");

        else printf("0 ");

    }

    printf("\n");

}

int main()

{

    read(n),read(m)//,read(S),read(T);

    init();

    two_SAT();

    return 0;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y),read(z);

        dadd(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    return 0;

}

7.二分图匹配（匈牙利）

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#define ll long long

using namespace std;

const int maxn=2000005;

const int maxm=5000005;

template <typename T>inline void read(T &x)

{

    T f=1,c=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    x=c*f;

}

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

    ll pri;

}edge[maxm];

struct E

{

    int l,r;

    ll v;

    friend bool operator < (E a,E b)

    {

        return a.v<b.v;

    }

}e[maxm];

struct node

{

    int p;ll v;

    node (){}

    node (int x,ll y):p(x),v(y){}

    friend bool operator < (node a,node b)

    {

        return a.v>b.v;

    }

};

int f[maxn];

int head[maxn];

ll dis[maxn];

ll va[maxn];

int dfn[maxn],low[maxn],posi[maxn];

ll src_num[maxn],src_cnt;

int my_stack[maxn],top=0;

int fa[maxn][25];

int dep[maxn];

int spe[maxn],nu;

int siz[maxn],son[maxn],ttop[maxn];

int inr[maxn],our[maxn];

int cur[maxn];

int pre[maxn];

ll lim[maxn];

bool used[maxn];

int cnt=1,deep;

int count_cut_line;

int n,m,S,T;

vector <int> v[maxn];

vector <int> peo[maxn];

vector <int> cut_point;

bool cmp(vector <int> a,vector <int> b)

{

    int lim=min(a.size(),b.size());

    for(int i=0;i<lim;i++)if(a[i]!=b[i])return a[i]<b[i];

    return a.size()<b.size();

}

void init()

{

    //for(int i=1;i<=n;i++)f[i]=i,head[i]=0;

    cnt=1;

}

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,int w)

{

    add(l,r,w),add(r,l,0);

}

void cost_add(int l,int r,ll w,ll p)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    edge[cnt].pri=p;

    head[l]=cnt++;

}

void cost_dadd(int l,int r,ll w,ll p)

{

    cost_add(l,r,w,p),cost_add(r,l,0,-p);

}

int findf(int x)

{

    return x==f[x]?x:f[x]=findf(f[x]);

}

void tree_dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,siz[x]=1,fa[x][0]=fx;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        tree_dfs(to,x);

        siz[x]+=siz[to],son[x]=(siz[son[x]]>siz[to])?son[x]:to;

    }

}

void tree_redfs(int x,int topx,int fx)

{

    ttop[x]=topx;

    if(son[x])tree_redfs(son[x],topx,x);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx||to==son[x])continue;

        tree_redfs(to,to,x);

    }

}

int quick_jump_LCA(int x,int y)//倍增LCA

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

int link_cut_LCA(int x,int y)//树剖LCA

{

    while(ttop[x]!=ttop[y])

    {

        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);

        x=fa[ttop[x]][0];

    }

    return dep[x]<dep[y]?x:y;

}

void di_tarjan(int x)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(!dfn[to])

        {

            di_tarjan(to);

            low[x]=min(low[x],low[to]);

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void ed_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(edge[i].val==fx)continue;

        if(!dfn[to])

        {

            ed_tarjan(to,edge[i].val);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<low[to])count_cut_line++;

        }else if(!posi[to])low[x]=min(low[x],dfn[to]);

    }

    if(dfn[x]==low[x])

    {

        src_cnt++;

        int t=0;

        while(t!=x)

        {

            t=my_stack[top--];

            src_num[src_cnt]++;

            posi[t]=src_cnt;

        }

    }

}

void po_tarjan(int x,int fx)

{

    my_stack[++top]=x,dfn[x]=low[x]=++deep;

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        if(!dfn[to])

        {

            int pre=top;

            po_tarjan(to,x);

            low[x]=min(low[x],low[to]);

            if(dfn[x]<=low[to])

            {

                src_cnt++,posi[x]++;

                int t=0;

                while(top!=pre)

                {

                    t=my_stack[top--];

                    peo[src_cnt].push_back(t);

                }

                peo[src_cnt].push_back(x);

                sort(peo[src_cnt].begin(),peo[src_cnt].end());

            }

        }else low[x]=min(low[x],dfn[to]);

    }

}

void kruscal()

{

    sort(e+1,e+m+1);

    int tot=0;ll ret=0;

    for(int i=1;i<=m;i++)

    {

        int f1=findf(e[i].l),f2=findf(e[i].r);

        if(f1==f2)continue;

        f[f1]=f2,tot++,ret+=e[i].v;

        if(tot==n-1)break;

    }

    if(tot==n-1)printf("%lld\n",ret);

    else printf("orz\n");

}

void min_dis_spfa(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0,used[st]=1;

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val)

            {

                dis[to]=dis[u]+edge[i].val;

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==INF)printf("2147483647 ");

        else printf("%lld ",dis[i]);

    }

}

void diji(int st)

{

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    priority_queue <node> M;

    M.push(node(st,0));

    while(!M.empty())

    {

        node temp=M.top();

        M.pop();

        int u=temp.p;

        if(used[u])continue;

        used[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(dis[to]>dis[u]+edge[i].val&&!used[to])dis[to]=dis[u]+edge[i].val,M.push(node(to,dis[to]));

        }

    }

    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);

}

void max_dis_spfa(int st)

{

    memset(dis,0,sizeof(dis));

    used[st]=1;

    dis[st]=src_num[st];

    queue <int> M;

    M.push(st);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=0;i<v[u].size();i++)

        {

            int to=v[u][i];

            if(dis[to]<dis[u]+src_num[to])

            {

                dis[to]=dis[u]+src_num[to];

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    ll ans=0;

    for(int i=1;i<=nu;i++)ans=max(ans,dis[posi[spe[i]]]);

    printf("%lld\n",ans);

}

void build_MST()

{

    kruscal();

}

void get_min_dis_road()

{

    //min_dis_spfa(S);

    diji(S);

}

void solve_LCA()

{

    tree_dfs(S,S),tree_redfs(S,S,S);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        read(x),read(y);

        printf("%d\n",link_cut_LCA(x,y));

    }

}

void direc_tarjan()//有向图tarjan

{

    for(int i=1;i<=n;i++)read(va[i]);

    read(S),read(nu);

    for(int i=1;i<=nu;i++)read(spe[i]);

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]==posi[to])continue;

            else v[posi[i]].push_back(posi[to]);

        }

    }

    max_dis_spfa(posi[S]);

}

void cut_line_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])ed_tarjan(i,-1);

    printf("%d ",count_cut_line);

    for(int i=1;i<=n;i++)

    {

        for(int j=head[i];j;j=edge[j].nxt)

        {

            int to=edge[j].to;

            if(posi[i]!=posi[to])inr[posi[to]]++;

        }

    }

    int s=0;

    for(int i=1;i<=src_cnt;i++)if(inr[i]==1)s++;

    printf("%d\n",(s+1)>>1);

}

void cut_point_tarjan()

{

    for(int i=1;i<=n;i++)if(!dfn[i])po_tarjan(i,-1),posi[i]--;

    for(int i=1;i<=n;i++)if(posi[i]>=1)cut_point.push_back(i);

    printf("%d\n",cut_point.size());

    for(int i=0;i<cut_point.size();i++)printf("%d ",cut_point[i]);

    printf("\n");

    printf("%d\n",src_cnt);

    sort(peo+1,peo+src_cnt+1,cmp);

    for(int i=1;i<=src_cnt;i++,printf("\n"))for(int j=0;j<peo[i].size();j++)printf("%d ",peo[i][j]);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool dinic_bfs()

{

    memset(dis,0,sizeof(dis));

    memcpy(cur,head,sizeof(head));

    dis[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[T];

}

ll dinic_dfs(int x,ll lim)

{

    if(x==T)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dinic_dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp,lim-=temp;

                edge[i].val-=temp,edge[ide(i)].val+=temp;

                if(!lim)break;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(dinic_bfs())ans+=dinic_dfs(S,INF);

    return ans;

}

void max_flow()

{

    printf("%lld\n",dinic());

}

bool EK_spfa()

{

    memset(pre,-1,sizeof(pre));

    memset(f,0,sizeof(f));

    memset(dis,0x3f,sizeof(dis));

    dis[S]=0,lim[S]=INF,used[S]=1;

    queue <int> M;

    M.push(S);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(edge[i].val&&dis[to]>dis[u]+edge[i].pri)

            {

                dis[to]=dis[u]+edge[i].pri;

                pre[to]=i,f[to]=u,lim[to]=min(lim[u],edge[i].val);

                if(!used[to])used[to]=1,M.push(to);

            }

        }

        used[u]=0;

    }

    return pre[T]!=-1;

}

void EK()

{

    ll maxf=0,minv=0;

    while(EK_spfa())

    {

        maxf+=lim[T],minv+=dis[T]*lim[T];

        int temp=T;

        while(temp!=S)edge[pre[temp]].val-=lim[T],edge[ide(pre[temp])].val+=lim[T],temp=f[temp];

    }

    printf("%lld %lld\n",maxf,minv);

}

void min_cost_max_flow()

{

    S=1,T=n;

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z,w;

        read(x),read(y),read(z),read(w);

        cost_dadd(x,y,z,w);

    }

    EK();

}

void two_SAT()

{

    for(int i=1;i<=m;i++)

    {

        int x,y,z,w;

        read(x),read(y),read(z),read(w);

        if(y==1&&w==1)add(x+n,z,0),add(z+n,x,0);

        else if(y==1)add(x+n,z+n,0),add(z,x,0);

        else if(w==1)add(x,z,0),add(z+n,x+n,0);

        else add(x,z+n,0),add(z,x+n,0);

    }

    n<<=1;

    for(int i=1;i<=n;i++)if(!dfn[i])di_tarjan(i);

    n>>=1;

    for(int i=1;i<=n;i++)if(posi[i]==posi[i+n]){printf("IMPOSSIBLE\n");exit(0);}

    printf("POSSIBLE\n");

    for(int i=1;i<=n;i++)

    {

        if(posi[i]<posi[i+n])printf("1 ");

        else printf("0 ");

    }

    printf("\n");

}

bool dfs(int x)

{

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(used[to])continue;

        used[to]=1;

        if(!f[to]||dfs(f[to])){f[to]=x;return 1;}

    }

    return 0;

}

int hungary()

{

    int ret=0;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n+m;j++)used[j]=0;

        if(dfs(i))ret++;

    }

    return ret;

}

void two_match()

{

    read(n),read(m),read(S);

    for(int i=1;i<=S;i++)

    {

        int x,y;

        read(x),read(y);

        if(x>n||y>m)continue;

        add(x,y+n,0),add(y+n,x,0);

    }

    printf("%d\n",hungary());

}

int main()

{

    two_match();

    return 0;

    read(n),read(m);//,read(S),read(T);

    init();

    for(int i=1;i<=m;i++)

    {

        int x,y;ll z;

        read(x),read(y),read(z);

        dadd(x,y,z);//,add(y,x,z);

        e[i].l=x,e[i].r=y,e[i].v=z;

    }

    return 0;

}

NOI模板复习组——图论部分的相关教程结束。