这里放了最基础的图论内容在本文中maxn为最大点数，maxm为最大边数.

链式前向星

以下代码存图所用链式前向星皆用这个模板

注意访问时的顺序与输入时是相反的。

struct edg
{
    int next,to,w;
}edge[maxm];//无向图是这里要<<1
int head[maxn],cnt=1;
inline void getin(int a,int b,int w)//加边
{
    edge[cnt]=(edg){head[a],b,w};
    head[a]=cnt++;
}
for(int j=head[tmp];j;j=edge[j].next)//访问tmp发出的边

拓扑排序

在建边时先预处理入度，即代码中的vin

int vin[maxn];//这个vin

queue<int>que;
for(int i=1;i<=n;i++)
if(!vin[i])
que.emplace(i);
while(!que.empty())
{
    int dc=que.front();
    for(int j=head[dc];j;j=edge[j].next)
    if(!(--vin[edge[j].to]))
    que.emplace(edge[j].to);
}

最短路

floyd

注意到最外层枚举的是中转点

int dis[maxn][maxn];//dis是邻接矩阵
for(int k=1;k<=n;k++)//k在这里！！
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(dis[i][j]>dis[i][k]+dis[k][j])
        {
            dis[i][j]=dis[i][k]+dis[k][j];
        }

dijkstra

论某个傻瓜曾经还在用手写堆

正确性？

设正确答案的 s−>is->i 的长度为 disidis_i，disijdis_{ij} 为 ii 到 jj 的边权。反证法，设 xx 为第一个使得在出队列时 disv+disvx>disxdis_v+dis_{vx}> dis_x 的，将 xx 加入堆的点为 tt(tt 此时已经求出正确答案)。此时正确路径上必有点 uu，vv 使得 u−>vu->v，v−>xv->x 不为空路径且 uu 已求出答案，vv 没有。注意到由于优先队列的性质，disxt+dist⩽disu+disuvdis_{xt}+dis_t\leqslant dis_u+dis_{uv}于是有：

disx=disu+disuv+disvx(dijkstra所有中转边⩾0)⩾disu+disuv⩾dist+disxt>disx\begin{split} dis_x &=dis_u+dis_{uv}+dis_{vx}\text{(dijkstra所有中转边$\geqslant 0$)}\\ &\geqslant dis_u+dis_{uv}\\ &\geqslant dis_t+dis_{xt}\\ &> dis_x \end{split}

显然没有大于自己的数，矛盾。

struct node
{
    int no,num;
    bool operator<(node y)const
    {
        return num>y.num;
    }
};
int dis[maxn];
bool bl[maxn];
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof dis);
    memset(bl,0,sizeof bl);
    priority_queue<node>que;
    dis[s]=0;
    que.emplace((node){s,0});
    while(!que.empty())
    {
        int dc=que.top().no;
        que.pop();
        if(bl[dc])continue;
        bl[dc]=true;
        for(register int j=head[dc];j;j=edge[j].next)
        if(dis[edge[j].to]>edge[j].w+dis[dc])
        {
            dis[edge[j].to]=edge[j].w+dis[dc];
            if(!bl[edge[j].to])que.emplace((node){edge[j].to,dis[edge[j].to]});
        }
    }
}

spfa+负环判断

int dis[maxn],tme[maxn];
bool bl[maxn];
bool spfa(int s)//返回s出发是否到达负环,可以返回false,代表不合法
{
    memset(dis,0x3f,sizeof dis);
    memset(bl,0,sizeof bl);
    memset(tme,0,sizeof tme);
    queue<int>que;
    que.emplace(s);
    bl[s]=true;dis[s]=0;
    while(!que.empty())
    {
        int dc=que.front();
        bl[dc]=false;que.pop();
        for(register int j=head[dc];j;j=edge[j].next)
        if(dis[edge[j].to]>dis[dc]+edge[j].w)
        {
            dis[edge[j].to]=dis[dc]+edge[j].w;
            tme[edge[j].to]=tme[dc]+1;
            if(tme[edge[j].to]>=n)return false;
            if(!bl[edge[j].to])que.emplace(edge[j].to),bl[edge[j].to]=true;
        }
    }
    return true;
}

差分约束

就一句话：对于 ai−aj⩽ka_i-a_j\leqslant{k} 的条件，我们只要由 jj 向 ii 建长度为 kk 的边，然后狂跑最短路就结束了。

0-1bfs

很不错的例题:P1948 [USACO08JAN]Telephone Lines S

bool bl[maxn];
int dis[maxn];
void bfs_01(int s)
{
    memset(dis,0x3f,sizeof dis);
    memset(bl,0,sizeof bl);
    deque<int>que;
    dis[s]=0;
    bl[s]=true;
    que.push_back(s);
    while(!que.empty())
    {
        int dc=que.front();
        que.pop_front();
        for(register int j=head[dc];j;j=edge[j].next)
        {
        if(dis[edge[j].to]>dis[dc]+edge[j].w)
        {
            dis[edge[j].to]=dis[dc]+edge[j].w;
            if(!bl[edge[j].to])
            if(edge[j].w)que.push_back(edge[j].to);
            else que.push_front(edge[j].to);
        }
        }
    }
}

关于DAG

显然，在DAG中，无论权值是否为负，比一个点拓扑序小的点全松弛完毕后，这个点的最短路就求出来了（因为显然每个点都只能从比自己拓扑序小的点走到）。

  • 代码几乎和拓扑排序一模一样，不放了。

联通性

有向图缩点（tarjan）

  • 显然将强连通分量都看成一个点后，新图是个DAG，这时（以下代码中的）belibel_i 即为 ii 所属的点反过来的拓扑序。

int tj,dfn[maxn],tot,low[maxn],bel[maxn],insta[maxn],sta[maxn],tcur;
void tarjan(int dc)
{
    dfn[dc]=low[dc]=++tj;
    sta[++tot]=dc;
    insta[dc]=true;
    for(register int j=head[dc];j;j=edge[j].next)
    if(!dfn[edge[j].to])
    {
        tarjan(edge[j].to);
        low[dc]=min(low[dc],low[edge[j].to]);
    }
    else if(insta[edge[j].to])low[dc]=min(low[dc],dfn[edge[j].to]);
    if(low[dc]==dfn[dc])
    {
        ++tcur;
        while(insta[dc])
        {
            insta[sta[tot]]=false;
            bel[sta[tot]]=tcur;
            tot--;
        }
    }
}

边双联通分量-tarjan（桥）[1]

相对点双联通分量，边双联通分量比较特殊，可以直接 lowx=dfnxlow_x=dfn_x。

连接两个边双联通分量的必为割边

模板P8436的代码如下：

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>//75760209
#include<ctime>
#include<climits>
#include<algorithm>
#include<vector>
#define fru(i,j,k) for(register int i=j;i<=k;i++)//for_register_up
#define frd(i,j,k) for(register int i=j;i>=k;i--)//for_register_down
#define pc(charx) putchar(charx)
#define finfout(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using ll = long long;
namespace usegetin{
    char c=' ';
    inline int in()
    {
        int x=0;bool w=false;
        while(!isdigit(c))
        {
            w|=c=='-';
            c=getchar();
        }
        while(isdigit(c))
        {
            x=(x<<1)+(x<<3)+(c^48);
            c=getchar();
        }
        return w?-x:x;
    }
    template<typename ty>
    void out(ty x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)out(x/10);
        putchar(x%10+48);
    }
}
using usegetin::in;using usegetin::out;
using namespace std;
const int maxn=500012,maxm=2000012;
int n,m,head[maxn],cnt=2;
struct edg
{
    int next,to;
    bool bml;
}edge[maxm<<1];
bool bl[maxn];
inline void getin(int a,int b)
{
    edge[cnt]=(edg){head[a],b,0};
    head[a]=cnt++;
}
vector<int>nl[maxn];
int low[maxn],dfn[maxn],tj,ans,sta[maxn],tot;
void tarjan(int dc)
{
    low[dc]=dfn[dc]=++tj;
    sta[++tot]=dc;
    for(register int j=head[dc];j;j=edge[j].next)
    if(!dfn[edge[j].to])
    {
        edge[j].bml=edge[j^1].bml=true;
        tarjan(edge[j].to);
        low[dc]=min(low[dc],low[edge[j].to]);
    }
    else if(!edge[j].bml)low[dc]=min(low[dc],dfn[edge[j].to]);
    if(low[dc]==dfn[dc])
    {
        ans++;
        while(sta[tot+1]^dc)nl[ans].emplace_back(sta[tot--]);
    }
}
int main()
{
    n=in();m=in();
    int t1,t2;
    fru(i,1,m)
    {
        t1=in();t2=in();
        getin(t1,t2);
        getin(t2,t1);
    }
    fru(i,1,n)
    if(!dfn[i])
    {
        tarjan(i);
    }
    out(ans);pc('\n');
    fru(i,1,ans)
    {
        out(nl[i].size());pc(' ');
        for(auto j:nl[i])
        {
            out(j);pc(' ');
        }pc('\n');
    }
    return 0;
}

点双联通分量-tarjan（割点）

连接两个点双联通分量的必为割点

模板：P8435。

代码如下：

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>//75760209
#include<ctime>
#include<climits>
#include<algorithm>
#include<vector>
#define fru(i,j,k) for(register int i=j;i<=k;i++)//for_register_up
#define frd(i,j,k) for(register int i=j;i>=k;i--)//for_register_down
#define pc(charx) putchar(charx)
#define finfout(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using ll = long long;
namespace usegetin{
    char c=' ';
    inline int in()
    {
        int x=0;bool w=false;
        while(!isdigit(c))
        {
            w|=c=='-';
            c=getchar();
        }
        while(isdigit(c))
        {
            x=(x<<1)+(x<<3)+(c^48);
            c=getchar();
        }
        return w?-x:x;
    }
    template<typename ty>
    void out(ty x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)out(x/10);
        putchar(x%10+48);
    }
}
using usegetin::in;using usegetin::out;
using namespace std;
const int maxn=500012,maxm=2000012;
int n,m,head[maxn],cnt=2;
struct edg
{
    int next,to;
}edge[maxm<<1];
inline void getin(int a,int b)
{
    edge[cnt]=(edg){head[a],b};
    head[a]=cnt++;
}
vector<int>nl[maxn];
int ans,low[maxn],dfn[maxn],tj,sta[maxn],tot;
void tarjan(int dc,int fadc)
{
    dfn[dc]=low[dc]=++tj;
    sta[++tot]=dc;
    int v;
    bool bl=false;
    for(register int j=head[dc];j;j=edge[j].next)
    if(!dfn[v=edge[j].to])
    {
        bl=true;
        tarjan(v,dc);
        low[dc]=min(low[dc],low[v]);
        if(dfn[dc]<=low[v])
        {
            ans++;
            while(sta[tot+1]^v)nl[ans].emplace_back(sta[tot--]);
            nl[ans].emplace_back(dc);
        }
    }
    else if(v^fadc)
    {
        // cout<<"d:"<<dc<<' '<<v<<' '<<fadc<<endl;
        low[dc]=min(low[dc],dfn[v]);
    }
    if(!fadc&&!bl)nl[++ans].emplace_back(dc);
}
int main()
{
    n=in();m=in();
    int t1,t2;
    fru(i,1,m)
    {
        t1=in();t2=in();
        getin(t1,t2);
        getin(t2,t1);
    }
    fru(i,1,n)
    if(!dfn[i])
    { 
        // cout<<"d:"<<i<<endl;
        tot=0;
        tarjan(i,0);
    }
    out(ans);pc('\n');
    fru(i,1,ans)
    {
        out(nl[i].size());pc(' ');
        for(auto j:nl[i])
        {
            out(j);pc(' ');
        }
        pc('\n');
    }
    return 0;
}

二分图

二分图最大匹配

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;using ll = long long;
namespace msi{
char c=' '; 
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
}
using msi::in;
const int maxn=100012;
//主体部分开始 
int n,m,e,bl[maxn],vt[maxn],ans,ml[maxn];
struct edg
{
    int next,to;
}edge[maxn];
int cnt=1,head[maxn];
inline void getin(int a,int b)
{
    edge[cnt]=(edg){head[a],b};
    head[a]=cnt++;
}
bool dfs(int dc,int fr)
{
    if(bl[dc]==fr)return false;
    bl[dc]=fr;
    for(int j=head[dc];j;j=edge[j].next)
    if(ml[edge[j].to]==0||dfs(ml[edge[j].to],fr))
    {
//        cout<<dc<<':'<<edge[j].to<<endl;
        ml[edge[j].to]=dc;
        return true;
    }
    return false;
}
int main()
{
    n=in();m=in();e=in();
    int t1,t2;
    fru(i,1,e)
    {
        t1=in();t2=in()+n;
        getin(t1,t2);getin(t2,t1);
    }
    fru(i,1,n)
    {
        ans+=dfs(i,i)?1:0;
    }
    printf("%d",ans);
    return 0;
}

二分图最大权完美匹配（KM算法）

模板题传送门

网络上讲得详细的题解比较少，洛谷题解较为详细却没有注释，因此打题的时候加了注释。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;using ll = long long;
namespace msi{
char c=' '; 
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
}
using msi::in;
const int maxn=512;
int n,m,fa[maxn],bl[maxn],br[maxn],ml[maxn],mr[maxn];
ll el[maxn][maxn],nl[maxn],nr[maxn],slk[maxn];//最小值建议比N条边最小可能值还小，不然选不存在的边反而更优秀就不好了
int st;
void gao(int v)
{
    // cout<<"gao"<<v<<endl;
    int t;
    while(v)
    {
        t=ml[fa[v]];ml[fa[v]]=v;mr[v]=fa[v];
        v=t;
    }
    // printf("mr");fru(i,1,n)printf("%d ",mr[i]);pc('\n');
    // printf("ml");fru(i,1,n)printf("%d ",ml[i]);pc('\n');
}
void bfs(void)
{
    memset(slk,0x3f,sizeof slk);
    queue<int>que;
    int dc;
    que.emplace(st);bl[st]=st;
    while(1)
    {
        while(!que.empty())
        {
            dc=que.front();que.pop();
            fru(i,1,n)
            if(br[i]^st&&(ll)nl[dc]+nr[i]-el[dc][i]<slk[i])//不然就是成环了，不然就是要更新的/在图中的
            {
                slk[i]=nl[dc]+nr[i]-el[dc][i];
                // if(i==6)cout<<dc<<' '<<i<<' '<<nl[dc]<<' '<<nr[i]<<' '<<el[dc][i]<<' '<<slk[i]<<endl;
                fa[i]=dc;//fa不一定在树中
                // cout<<"setfa"<<i<<' '<<dc<<endl;
                if(!slk[i])//在图中的
                {
                    br[i]=st;
                    if(!mr[i]){gao(i);return ;}
                    else if(bl[mr[i]]!=st){bl[mr[i]]=st;que.emplace(mr[i]);}
                }
            }
        }
        dc=0x3f3f3f3f;
        fru(i,1,n)if(br[i]!=st&&dc>slk[i])dc=slk[i];
        fru(i,1,n)
        {
            if(bl[i]==st)nl[i]-=dc;
            if(br[i]==st)nr[i]+=dc;
            else slk[i]-=dc;//正好维护哪个slk变成了0
        }
        fru(i,1,n)
        if(br[i]^st&&!slk[i])
        {
            br[i]=st;
            if(!mr[i]){gao(i);return ;}
            else if(bl[mr[i]]!=st){bl[mr[i]]=st;que.emplace(mr[i]);}
        }
    }
}
ll ans;
int main()
{
    // fio();
    n=in();m=in();
    memset(el,-0x3f,sizeof el);
    memset(nl,-0x3f,sizeof nl);
    // cout<<el[0][0]<<endl;
    int t1,t2,t3;
    fru(i,1,m)
    {
        t1=in();t2=in();t3=in();
        el[t1][t2]=t3;
        nl[t1]=max(nl[t1],el[t1][t2]);
    }
    for(st=1;st<=n;st++)bfs();
    fru(i,1,n)
    {
        // cout<<"nl"<<nl[i]<<' '<<nr[i]<<endl;
        ans+=nl[i]+nr[i];
    }
    printf("%lld\n",ans);
    fru(i,1,n)printf("%d ",mr[i]);
    return 0;
}

关于树

最近公共祖先（LCA）

我知道树链剖分自带这个。所以这里只有倍增……

预处理部分：

int fa[20][maxn],depth[maxn],lg[maxn];
//加在main中（默认1为根）
lg[0]=-1;
fru(i,1,n)lg[i]=lg[i>>1]+1;
dfs(1,0);
//dfs
void dfs(int dc,int fadc)
{
    fa[0][dc]=fadc;
    fru(i,1,lg[depth[dc]])fa[i][dc]=fa[i-1][fa[i-1][dc]];
    for(register int j=head[dc];j;j=edge[j].next)
    if(edge[j].to!=fadc)
    {
        depth[edge[j].to]=depth[dc]+1;
        dfs(edge[j].to,dc);
    }
}

干活部分：

int lca(int xx,int yy)
{
    if(depth[xx]<depth[yy])swap(xx,yy);
    while(depth[xx]>depth[yy])xx=fa[lg[depth[xx]-depth[yy]]][xx];
    if(xx==yy)return xx;
    frd(i,lg[depth[xx]],0)if(fa[i][xx]!=fa[i][yy])
    {
        xx=fa[i][xx];yy=fa[i][yy];
    }
    return fa[0][xx];
}

树链剖分

//核心代码
int fa[maxn],size[maxn],dep[maxn],son[maxn],top[maxn],dfn[maxn],tot;
void dfs1(int dc)
{
    size[dc]=1;
    dep[dc]=dep[fa[dc]]+1;
    for(register int j=head[dc];j;j=edge[j].next)
    if(edge[j].to^fa[dc])
    {
        fa[edge[j].to]=dc;
        dfs1(edge[j].to);
        size[dc]+=size[edge[j].to];
        if(size[son[dc]]<size[edge[j].to])son[dc]=edge[j].to;
    }
}
void dfs2(int dc,int dctop)
{
    top[dc]=dctop;
    dfn[dc]=++tot;
    if(!son[dc])return ;
    dfs2(son[dc],dctop);
    for(register int j=head[dc];j;j=edge[j].next)
    if(edge[j].to^son[dc]&&edge[j].to^fa[dc])
    {
        dfs2(edge[j].to,edge[j].to);
    }
}

关于网络流

存个模板，放个链接.

最大流/最小割

最小割模型：若题目可以转为为一些点，每个点有双态，把点分在两个态中会产生花费，并且条件可以表示为“若 A 在 C 态，则 B 也在 C 态”的，可以考虑使用最小割求最小花费。

EK

namespace ek{//注意到有bl等数组，建议把所有东西放入一个namespace，避免与最短路等的变量名冲突。
bool bl[maxn];
int pre[maxn];
bool bfs(void)
{
    queue<int>que;
    memset(bl,0,sizeof bl);
    que.push(s);
    bl[s]=true;
    while(!que.empty())
    {
        int dc=que.front();
        que.pop();
        for(register int i=head[dc];i;i=edge[i].next)
        if(!bl[edge[i].to]&&edge[i].w)
        {
            pre[edge[i].to]=i;
            //if(i==edge[i].to)
            //ccout<<"kamuamua";
            if(!(edge[i].to^t))return true;
            que.push((edge[i].to));
            bl[edge[i].to]=true;
        }
    }
    return false;
}
ll ek(void)
{
    int minn;
    ll ans=0;
    while(bfs())
    {
        minn=0x7f7f7f7f;
        for(register int i=t;i^s;i=edge[pre[i]^1].to)
        {
            minn=(minn>edge[pre[i]].w)?edge[pre[i]].w:minn;
            //cout<<i<<' '<<pre[i].point<<' '<<pre[i].edge<<endl;
        }
        for(register int i=t;i^s;i=edge[pre[i]^1].to)
        {
            edge[pre[i]].w-=minn;
            edge[pre[i]^1].w+=minn;
        }
        ans+=minn;
    }
    return ans;
}
}

DINIC

namespace dinic{//同上
bool bl[maxn];int cur[maxn],dis[maxn];
int S,T;
bool bfs(void)
{
    memset(bl,0,sizeof bl);
    queue<int>que;
    bl[S]=true;
    dis[S]=0;
    que.emplace(S);
    while(!que.empty())
    {
        int dc=que.front();
        que.pop();
        for(register int j=head[dc];j;j=edge[j].next)
        if(!bl[edge[j].to]&&edge[j].w)
        {
            dis[edge[j].to]=dis[dc]+1;
            bl[edge[j].to]=true;
            que.emplace(edge[j].to);
        }
    }
    return bl[T];
}
ll dfs(int dc,ll flow)
{
    if(dc==T||flow==0)return flow;//推完流量就别推了，不然会出事。
    ll dcflow=0,f;
    for(register int j=cur[dc];j;j=edge[j].next)
    {
        cur[dc]=j;
        if(edge[j].w&&dis[edge[j].to]==dis[dc]+1&&(f=dfs(edge[j].to,min((ll)edge[j].w,flow))))//水太少，管子太细，流量都不会多hhh
        {
            dcflow+=f;
            flow-=f;
            edge[j].w-=f;
            edge[j^1].w+=f;
        }
    }
    return dcflow;
}
ll dinic(void)
{
    ll ans=0;
    while(bfs())
    {
        fru(i,1,n)cur[i]=head[i];
        ans+=dfs(S,LLONG_MAX);
    }
    return ans;
}
}

费用流/最小费用最大流

dinic+spfa

namespace dinic{
bool bl[maxn];int cur[maxn],dis[maxn];
bool bfs(void)
{
    fru(i,1,n)
    {
        bl[i]=0;
        dis[i]=INT_MAX-2000;
    }
    queue<int>que;
    bl[s]=true;
    dis[s]=0;
    que.emplace(s);
    while(!que.empty())
    {
        int dc=que.front();
        bl[dc]=false;
        que.pop();
        for(register int j=head[dc];j;j=edge[j].next)
        if(edge[j].w1&&dis[edge[j].to]>dis[dc]+edge[j].w2)
        {
            dis[edge[j].to]=dis[dc]+edge[j].w2;
            if(!bl[edge[j].to])
            {
                bl[edge[j].to]=true;
                que.emplace(edge[j].to);
            }
        }
    }
    return dis[t]!=INT_MAX-2000;
}
int dfs(int dc,int flow)
{
    if(dc==t||flow==0)return flow;//推完流量就别推了，不然会出事。
    int dcflow=0,f;
    bl[dc]=1;
    for(register int j=cur[dc];j;j=edge[j].next)
    {
        cur[dc]=j;
        if(!bl[edge[j].to]&&dis[edge[j].to]==dis[dc]+edge[j].w2&&(f=dfs(edge[j].to,min(edge[j].w1,flow))))//注意用visit数组避免0环
        {
            dcflow+=f;
            flow-=f;
            edge[j].w1-=f;
            edge[j^1].w1+=f;
        }
    }
    bl[dc]=0;
    return dcflow;
}
pair<int,int> dinic(void)
{
    int as1=0,as2=0,tp;
    while(bfs())
    {
        fru(i,1,n)
        {
            cur[i]=head[i];bl[i]=0;
        }
        tp=dfs(s,INT_MAX);
        as1+=tp;as2+=dis[t]*tp;
    }
    return make_pair(as1,as2);
}
}

  1. 差分远比看起来难写，差评！ ↩︎