时间戳

首页 > 技术文章 > 【模板整合计划】图论

【模板整合计划】图论

Xing-Ling 2019-11-12 18:00 原文

【模板整合计划】图论

一：【拓扑排序】

最大食物链计数 \(\text{[P4017]}\)

#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=5e5+3,inf=2e9,P=80112002;
int n,m,x,y,o,ans,dp[N],ru[N],chu[N],head[N];
struct QAQ{int to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}

int main(){
    in(n),in(m);
    while(m--)in(x),in(y),add(x,y),++ru[y],++chu[x];
    for(Re i=1;i<=n;++i)if(!ru[i])dp[i]=1,Q.push(i);
    while(!Q.empty()){
        Re x=Q.front();Q.pop();
        for(Re i=head[x],to;i;i=a[i].next){
            (dp[to=a[i].to]+=dp[x])%=P;
            if(!--ru[to])Q.push(to);
        }
    }
    for(Re i=1;i<=n;++i)if(!chu[i])(ans+=dp[i])%=P;
    printf("%d\n",ans%P);
}

二：【最短路】

1.【最短路】

(1).【Floyed】

\(\text{Floyd}\) 求最短路 \(\text{[AcWing856]}\)

#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=203,inf=2e9;
int n,m,x,y,z,T,dis[N][N];
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
int main(){
    in(n),in(m),in(T);
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=n;++j)
            dis[i][j]=inf;
    for(Re i=1;i<=n;++i)dis[i][i]=0;
    while(m--)in(x),in(y),in(z),dis[x][y]=min(dis[x][y],z);
    for(Re k=1;k<=n;++k)
        for(Re i=1;i<=n;++i)
            for(Re j=1;j<=n;++j)    
                if(dis[i][k]!=inf&&dis[k][j]!=inf)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    while(T--){
        in(x),in(y);
        if(dis[x][y]==inf)puts("impossible");
        else printf("%d\n",dis[x][y]);
    }
}

(2).【Dijkstra】

【模板】单源最短路径（标准版）\(\text{[P4779]}\)

#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=1e5+5,inf=2e9;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void dijkstra(Re st){
    for(Re i=0;i<=n;++i)dis[i]=inf;
    dis[st]=0,Q.push((QWQ){st,0});
    while(!Q.empty()){
        x=Q.top().x,Q.pop();
        if(pan[x])continue;
        pan[x]=1;
        for(Re i=head[x];i;i=a[i].next)
            if(dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w;
                Q.push((QWQ){to,dis[to]});
            }
    }
}
int main(){
    in(n),in(m),in(st);
    while(m--)in(x),in(y),in(z),add(x,y,z);
    dijkstra(st);
    for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}

(3).【SPFA】

【模板】单源最短路径（弱化版）\(\text{[P3371]}\)

#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=5e5+5,inf=2147483647;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
queue<int>Q;
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void SPFA(Re st){
    for(Re i=0;i<=n;++i)dis[i]=inf;
    dis[st]=0,pan[st]=1,Q.push(st);
    while(!Q.empty()){
        x=Q.front(),Q.pop();
        pan[x]=0;
        for(Re i=head[x];i;i=a[i].next)
            if(dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
}
int main(){
    in(n),in(m),in(st);
    while(m--)in(x),in(y),in(z),add(x,y,z);
    SPFA(st);
    for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}

2.【最小环】

\(\text{Sightseeing trip}\) \(\text{[Poj1734]}\)

#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=1e8;
int n,m,x,y,z,ans,Ans[N],a[N][N],g[N][N],dis[N][N];
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void get(Re i,Re j){
    Re k=g[i][j];if(!k)return;
    get(i,k),Ans[++Ans[0]]=k,get(k,j);
}
int main(){
    in(n),in(m);
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=n;++j)
            dis[i][j]=a[i][j]=inf;
    for(Re i=1;i<=n;++i)dis[i][i]=a[i][i]=0;
    while(m--)in(x),in(y),in(z),dis[x][y]=dis[y][x]=a[x][y]=a[y][x]=min(a[x][y],z);
    ans=inf;
    for(Re k=1;k<=n;++k){
        for(Re i=1;i<k;++i)
            for(Re j=i+1,tmp;j<k;++j)
                if((tmp=dis[i][j]+a[j][k]+a[k][i])<ans){
                    ans=tmp,Ans[0]=0;
                    Ans[++Ans[0]]=i;
                    get(i,j);
                    Ans[++Ans[0]]=j;
                    Ans[++Ans[0]]=k;
                }
        for(Re i=1;i<=n;++i)
            for(Re j=1,tmp;j<=n;++j)
                if((tmp=dis[i][k]+dis[k][j])<dis[i][j])
                    dis[i][j]=tmp,g[i][j]=k;
    }
    if(ans==inf)puts("No solution.");
    else for(Re i=1;i<=Ans[0];++i)printf("%d ",Ans[i]); 
}

3.【次短路 (SPFA)】

路障 \(\text{Roadblocks}\) \(\text{[P2865]}\)

#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=1e5+3,inf=1e9;
int n,m,x,y,z,o,pan[N],head[N],dis[N][2];
struct QAQ{int w,to,next;}a[M<<1];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void SPFA(Re st){
    for(Re i=0;i<=n;++i)dis[i][0]=dis[i][1]=inf;
    dis[st][0]=0,pan[st]=1,Q.push(st);
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to,tmp;i;i=a[i].next){
            if(dis[to=a[i].to][0]>(tmp=dis[x][0]+a[i].w)){
                dis[to][1]=dis[to][0];
                dis[to][0]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
            if(dis[to][1]>(tmp=dis[x][0]+a[i].w)&&tmp>dis[to][0]){
                dis[to][1]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
            if(dis[to][1]>(tmp=dis[x][1]+a[i].w)){
                dis[to][1]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
        }
    }
}
int main(){
    in(n),in(m);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
    SPFA(1);
    printf("%d\n",dis[n][1]);
}

三：【最小生成树】

1.【最小生成树】

1.【Kruscal】

【模板】最小生成树 \(\text{[P3366]}\)

#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3;
int n,m,ans,fa[N];
struct QAQ{int x,y,w;inline bool operator<(const QAQ &O)const{return w<O.w;};}A[M];
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
    in(n),in(m);
    for(Re i=1;i<=n;++i)fa[i]=i;
    for(Re i=1;i<=m;++i)in(A[i].x),in(A[i].y),in(A[i].w);
    sort(A+1,A+m+1);
    for(Re i=1,t=0;i<=m&&t<n-1;++i){
        Re x=find(A[i].x),y=find(A[i].y);
        if(x!=y)++t,ans+=A[i].w,fa[x]=y;
    }
    printf("%d",ans);
}

2.【Prim】

【模板】最小生成树 \(\text{[P3366]}\)

#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3,inf=2e9;
int x,y,z,n,m,o,ans,pan[N],dis[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ o)const{return d>o.d;};};
priority_queue<QWQ>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void Prim(){
    for(Re i=0;i<=n;++i)pan[i]=0,dis[i]=inf;
    Re t=0;Q.push((QWQ){1,dis[1]=0});
    while(!Q.empty()&t<n){
        Re x=Q.top().x;Q.pop();
        if(pan[x])continue;
        pan[x]=1,++t,ans+=dis[x];
        for(Re i=head[x],to;i;i=a[i].next)
            if(dis[to=a[i].to]>a[i].w)Q.push((QWQ){to,dis[to]=a[i].w});
    }
}
int main(){
    in(n),in(m);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
    Prim();
    printf("%d",ans);
}

(3).【LCT】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=205003;
int n,m,x,y,z,id,ans,id_O,v[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
    #define pl tr[p].ps[0]
    #define pr tr[p].ps[1]
    #define pf tr[p].fa
    int Q[N];
    struct QAQ{int fa,mx,mxw,tag,ps[2];}tr[N];
    inline void pushup(Re p){
        tr[p].mx=v[p],tr[p].mxw=p;
        if(pl&&tr[pl].mx>tr[p].mx)tr[p].mx=tr[pl].mx,tr[p].mxw=tr[pl].mxw;
        if(pr&&tr[pr].mx>tr[p].mx)tr[p].mx=tr[pr].mx,tr[p].mxw=tr[pr].mxw;
    }
    inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
    inline void pushdown(Re p){
        if(tr[p].tag){
            if(pl)updata(pl);
            if(pr)updata(pr);
            tr[p].tag=0;
        }
    }
    inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
    inline int which(Re p){return tr[pf].ps[1]==p;}
    inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
    inline void rotate(Re p){
        Re fa=pf,fas=which(p);
        Re pa=tr[fa].fa,pas=which(fa);
        Re x=tr[p].ps[fas^1];
        if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
        connect(x,fa,fas),connect(fa,p,fas^1);
        pushup(fa),pushup(p);
    }
    inline void splay(Re p){
        Re x=p,t=0;Q[++t]=x;
        while(nort(x))Q[++t]=x=tr[x].fa;
        while(t)pushdown(Q[t--]);
        for(Re fa;nort(p);rotate(p))
            if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
    }
    inline void access(Re p){
        for(Re son=0;p;son=p,p=pf)
            splay(p),pr=son,pushup(p);
    }
    inline void makeroot(Re p){access(p),splay(p),updata(p);}
    inline int findroot(Re p){
        access(p),splay(p),pushdown(p);
        while(pl)pushdown(p=pl);
        return p;
    }
    inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
    inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
    inline void cut(Re x,Re y){
        makeroot(x);
        if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
            tr[x].fa=tr[y].ps[0]=0,pushup(y);
    }
    inline int judge(Re x,Re y){makeroot(x);return findroot(y)==x;}
    inline void sakura(Re x,Re y,Re z,Re id){
        if(!judge(x,y))link(x,id),link(id,y),ans+=z;
        else{
            split(x,y);Re mx=tr[y].mx,mxw=tr[y].mxw;
            if(z<mx){
                ans+=z-mx,splay(mxw);
                tr[tr[mxw].ps[0]].fa=tr[tr[mxw].ps[1]].fa=0;
                link(x,id),link(id,y);
            }
        }
    }
}LCT;
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m);
    while(m--)in(x),in(y),in(z),v[id=++id_O+n]=z,LCT.sakura(x,y,z,id);
    printf("%d\n",ans);
}

2.【严格次小生成树】

【模板】严格次小生成树 \(\text{[P4180]}\)

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,M=5e5+3,logN=19,inf=2e9;
int T,n,m,o,root,fa[N],head[N],Tree[M],M1[N][23],M2[N][23];LL MinTree;
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,y,w;inline bool operator<(QWQ O)const{return w<O.w;}}A[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
struct LCA{
    int deep[N],ant[N][23];
    inline void dfs(Re x,Re fa){
        deep[x]=deep[fa]+1,ant[x][0]=fa;
        for(Re i=1;(1<<i)<=deep[x];++i){
            ant[x][i]=ant[ant[x][i-1]][i-1];
            M1[x][i]=max(M1[x][i-1],M1[ant[x][i-1]][i-1]);
            M2[x][i]=max(M2[x][i-1],M2[ant[x][i-1]][i-1]);
            if(M1[x][i-1]!=M1[ant[x][i-1]][i-1])
                M2[x][i]=max(M2[x][i],min(M1[x][i-1],M1[ant[x][i-1]][i-1]));
        }
        for(Re i=head[x],to;i;i=a[i].next)
            if((to=a[i].to)!=fa)M1[to][0]=a[i].w,M2[to][0]=-inf,dfs(to,x);
    }
    inline int lca(Re x,Re y){
        if(deep[x]>deep[y])swap(x,y);
        for(Re i=logN;i>=0;--i)if(deep[x]<=deep[y]-(1<<i))y=ant[y][i];
        if(x==y)return y;
        for(Re i=logN;i>=0;--i)
            if(ant[x][i]^ant[y][i])x=ant[x][i],y=ant[y][i];
        return ant[x][0];
    }
    inline int ask_max(Re x,Re Ant,Re w){
        Re ans=-inf;
        for(Re i=logN;i>=0;--i)
            if(deep[ant[x][i]]>=deep[Ant]){
                if(w!=M1[x][i])ans=max(ans,M1[x][i]);
                else ans=max(ans,M2[x][i]);
                x=ant[x][i];
            }
        return ans;
    }
}T1;
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void kruscal(){
    sort(A+1,A+m+1);
    for(Re i=1;i<=n;++i)fa[i]=i;
    for(Re i=1;i<=m;++i){
        Re x=A[i].x,y=A[i].y,w=A[i].w;
        if(find(x)!=find(y)){
            MinTree+=w,Tree[i]=1;
            add(x,y,w),add(y,x,w);
            fa[find(x)]=find(y);
        }
    }
}
int main(){
    in(n),in(m),root=1;
    for(Re i=1;i<=m;++i)in(A[i].x),in(A[i].y),in(A[i].w);
    kruscal();
    M1[root][0]=0,M2[root][0]=-inf,T1.dfs(root,0);
    LL ans=1e17;
    for(Re i=1;i<=m;++i)
        if(!Tree[i]){
            Re x=A[i].x,y=A[i].y,w=A[i].w,lca=T1.lca(x,y);
            ans=min(ans,MinTree+w-max(T1.ask_max(x,lca,w),T1.ask_max(y,lca,w)));
        }
    printf("%lld",ans);
}

3.【最小生成树计数】

最小生成树计数 \(\text{[JSOI2008] [P4208]}\)

不会，先咕着。

4.【曼哈顿距离最小生成树】

【模板】 \(\text{Object Clustering [Poj3241]}\)

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const LL N=1e4+3;
inline void in(Re &x){
    int f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
}
LL n,m,x,y,t,K,Ans,b[N];
struct QAQ{LL x,y,v;inline bool operator<(const QAQ &O)const{return v<O.v;}}a[N<<3];
struct Point{LL x,y,id;inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}}P[N];
inline LL Abs(LL a){return a<0?-a:a;}
inline LL Dis(Re x,Re y){return Abs(P[x].x-P[y].x)+Abs(P[x].y-P[y].y);}
struct BIT{
    LL n,C[N],id[N];
    inline void CL(){memset(C,127,sizeof(C));}
    inline void add(Re x,Re v,Re ID){while(x){if(v<C[x])C[x]=v,id[x]=ID;x-=x&-x;}}
    inline LL ask(Re x){Re Min=1e18,ID=0;while(x<=n){if(C[x]<Min)Min=C[x],ID=id[x];x+=x&-x;}return ID;}
}TR;
inline LL find_(Re x){
    Re l=1,r=t;
    while(l<r){
        Re mid=(l+r+1)>>1;
        if(b[mid]<=x)l=mid;
        else r=mid-1;
    }
    return l;
}
LL fa[N];
inline LL find(Re x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void kruscal(){
    for(Re O=1;O<=4;++O){
        if(!(O&1))for(Re i=1;i<=n;++i)swap(P[i].x,P[i].y);
        else if(O==3)for(Re i=1;i<=n;++i)P[i].x*=-1;
        sort(P+1,P+n+1);
        for(Re i=1;i<=n;++i)b[i]=P[i].y-P[i].x;
        sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b-1;
        TR.n=t,TR.CL();
        for(Re i=n;i>=1;--i){
            Re I=find_(P[i].y-P[i].x),j=TR.ask(I);
            if(j)a[++m]=(QAQ){P[i].id,P[j].id,Dis(i,j)};
            TR.add(I,P[i].x+P[i].y,i);
        }
    }
    sort(a+1,a+m+1);
    for(Re i=1;i<=n;++i)fa[i]=i;
    for(Re i=1,t=0;i<=m&&t<n-1;++i)if((x=find(a[i].x))!=(y=find(a[i].y))){
        fa[x]=y,Ans+=a[i].v;
        if(++t==K)printf("%lld\n",a[i].v);//输出生成树上第K小的边
    }
}
int main(){
    in(n),in(K),K=n-1-K+1;//把第K大转换为第n-K小
    for(Re i=1;i<=n;++i)in(P[i].x),in(P[i].y),P[i].id=i;
    kruscal();
}

四：【树论】

五：【负环与差分约束】

1.【负环的判定】

【模板】负环 \(\text{[P3385]}\)

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2003,M=3e5+3,inf=2e9;
int n,m,x,y,z,o,T,pan[N],chu[N],dis[N],head[N];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int SPFA(Re st){
    for(Re i=1;i<=n;++i)dis[i]=inf,chu[i]=pan[i]=0;
    while(!Q.empty())Q.pop();
    Q.push(st),dis[st]=0,chu[st]=0,pan[st]=1;
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w;
                if((chu[to]=chu[x]+1)>=n)return 1;
//                if(++chu[to]>=n)return 1;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return 0;
}
int main(){
    in(T);
    while(T--){
        in(n),in(m),memset(head,0,sizeof(head)),o=0;
        while(m--){in(x),in(y),in(z),add(x,y,z);if(z>=0)add(y,x,z);}
        puts(SPFA(1)?"YES":"NO");
    }
}

2.【差分约束】

【模板】糖果 \(\text{[P3275]}\)

#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=3e5+5,inf=2e9;
int x,y,n,m,o,op,chu[N],dis[N],pan[N],head[N];long long ans;
struct QAQ{int w,to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline int SPFA(Re st,Re ed){//求最小值跑最长路 
    for(Re i=0;i<=n;++i)dis[i]=-inf,chu[i]=0;
    dis[st]=0,chu[st]=pan[st]=1,Q.push(st);
    while(!Q.empty()){
        x=Q.front(),Q.pop();
        pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(dis[to=a[i].to]<dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w;
                if((chu[to]=chu[x]+1)>n+1)return 1;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return 0;
}
int main(){
    in(n),in(m);
    for(Re i=n;i>=1;--i)add(0,i,1); //a[i]>=a[0]=1,a[i]-a[0]>=1
    while(m--){
        in(op),in(x),in(y);
        if(op<2)add(y,x,0),add(x,y,0);//a[x]==a[y]: a[x]-a[y]>=0且a[y]-a[x]>=0
        else if(op<3)add(x,y,1);//a[x]<a[y]: a[y]-a[x]>=1
        else if(op<4)add(y,x,0);//a[x]>=a[y]: a[x]-a[y]>=0
        else if(op<5)add(y,x,1);//a[x]>a[y]: a[x]-a[y]>=1
        else add(x,y,0);//a[x]<=a[y]: a[y]-a[x]>=0
        if(!(op%2)&&x==y){puts("-1");return 0;}
    }
    if(SPFA(0,n))puts("-1");
    else{
        for(Re i=1;i<=n;++i)ans+=dis[i];
        printf("%lld",ans);
    }
}

六：【图的连通性】

【模板整合计划】图论—图的连通性

七：【二分图】

1.【二分图判定（染色法）】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2003,M=1e6+3;
int n,m,x,y,h,t,o,T,O,Q[N],head[N],color[N];
struct QAQ{int to,next;}a[M<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int judge(){
    for(Re i=1;i<=n;++i)
        if(!color[i]){
            h=1,t=0,Q[++t]=i,color[i]=1;
            while(h<=t){
                Re x=Q[h++];
                for(Re j=head[x],to;j;j=a[j].next)
                    if(!color[to=a[j].to])color[to]=3-color[x],Q[++t]=to;
                    else if(color[to]==color[x])return 0;
            }
        }
    return 1;
}
int main(){
    in(T);
    while(T--){
        memset(color,0,sizeof(color));
        memset(head,0,sizeof(head));
        in(n),in(m),o=0;
        while(m--)in(x),in(y),add(x,y),add(y,x);
        printf("Scenario #%d:\n",++O);
        puts(judge()?"No suspicious bugs found!\n":"Suspicious bugs found!\n");
    }
}

2.【二分图最大匹配】

【模板】二分图匹配 \(\text{[P3386]}\)

#include<cstring>
#include<cstdio>
#define Re register int
const int N=1003;
int o,n,m,e,x,y,ans,pan[N],head[N],match[N];
struct QAQ{int to,next;}a[N*N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline int dfs(Re x){
    for(Re i=head[x],to;i;i=a[i].next)
        if(!pan[to=a[i].to]){
            pan[to]=1;
            if(!match[to]||dfs(match[to])){
                match[to]=x;return 1;
            }
        }
    return 0;
}
int main(){
    in(n),in(m),in(e);
    while(e--){in(x),in(y);if(x<=n&&y<=m)add(x,y);}
    for(Re i=1;i<=n;++i){
        memset(pan,0,sizeof(pan));
        ans+=dfs(i);
    }
    printf("%d",ans);
}

3.【最小点覆盖】

  • 最小点覆盖 \(=\) 最大匹配

4.【最小路径点覆盖】

  • 最小路径点覆盖 \(=n\) \(-\) 最大匹配

5.【最大独立集】

  • 最大独立集 \(=n\) \(-\) 最大匹配

6.【二分图带权匹配】

【KM】

八：【网络流】

1.【最大流】

【模板】网络最大流 \(\text{[P3376]}\)

(1).【EK】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+3,M=1e5+3,inf=2e9;
int x,y,z,o=1,n,m,h,t,st,ed,maxflow,Q[N],cyf[N],pan[N],pre[N],head[N];
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
    for(Re i=0;i<=n;++i)pan[i]=0;
    h=1,t=0,pan[st]=1,Q[++t]=st,cyf[st]=inf;//注意起点cfy的初始化
    while(h<=t){
        Re x=Q[h++];
        for(Re i=head[x],to;i;i=a[i].next)
            if(a[i].flow&&!pan[to=a[i].to]){//增广路上的每条边残留容量均为正
                cyf[to]=min(cyf[x],a[i].flow);
                //用cyf[x]表示找到的路径上从S到x途径边残留容量最小值
                Q[++t]=to,pre[to]=i,pan[to]=1;//记录选择的边在链表中的下标
                if(to==ed)return 1;//如果达到终点，说明最短增广路已找到，结束bfs
            }
    }
    return 0;
}
inline void EK(Re st,Re ed){
    while(bfs(st,ed)==1){
        Re x=ed;maxflow+=cyf[ed];//cyf[ed]即为当前路径上边残留容量最小值
        while(x!=st){//从终点开始一直更新到起点
            Re i=pre[x];
            a[i].flow-=cyf[ed];
            a[i^1].flow+=cyf[ed];
            x=a[i^1].to;//链表特性，反向边指向的地方就是当前位置的父亲
        }
    }
}
int main(){
    in(n),in(m),in(st),in(ed);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,0);
    EK(st,ed);
    printf("%d",maxflow);
}

(2).【Dinic】

【模板】网络最大流 \(\text{[P3376]}\)

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+3,M=1e5+3,inf=2147483647;
int x,y,z,o=1,n,m,h,t,st,ed,Q[N],cur[N],dis[N],head[N];long long maxflow;
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){//bfs求源点到所有点的最短路
    for(Re i=0;i<=n;++i)cur[i]=head[i],dis[i]=0;//当前弧优化cur=head
    h=1,t=0,dis[st]=1,Q[++t]=st;
    while(h<=t){
        Re x=Q[h++],to;
        for(Re i=head[x];i;i=a[i].next)
            if(a[i].flow&&!dis[to=a[i].to]){
                dis[to]=dis[x]+1,Q[++t]=to;
                if(to==ed)return 1;
            }
    }
    return 0;
}
inline int dfs(Re x,Re flow){//flow为剩下可用的流量
    if(!flow||x==ed)return flow;//发现没有流了或者到达终点即可返回
    Re tmp=0,to,f;
    for(Re i=cur[x];i;i=a[i].next){
        cur[x]=i;//当前弧优化cur=i
        if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
//若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow-=f,a[i^1].flow+=f;
            tmp+=f;//记录终点已经从x这里获得了多少流
            if(!(flow-tmp))break;
//1\. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
//而此时边i很可能还没有被榨干，所以cur[x]即为i。
//2\. 下面儿子的容量先被榨干。不会break，但边i成了废边。
//于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
//直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st,Re ed){
    Re flow=0;
    while(bfs(st,ed))maxflow+=dfs(st,inf);
}
int main(){
    in(n),in(m),in(st),in(ed);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,0);
    Dinic(st,ed);
    printf("%lld",maxflow);
}

2.【最小割】

  • 最小割 \(=\) 最大流

3.【费用流】

(1).【EK】

【模板】最小费用最大流 \(\text{[P3381]}\)

#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5003,M=5e4+3,inf=2e9;
int x,y,z,w,o=1,n,m,h,t,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
    for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
    Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w,pre[to]=i;
                cyf[to]=min(cyf[x],a[i].flow);
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
    while(SPFA(st,ed)){
        Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
        while(x!=st){//和最大流一样的更新
            Re i=pre[x];
            a[i].flow-=cyf[ed];
            a[i^1].flow+=cyf[ed];
            x=a[i^1].to;
        }
    }
}
int main(){
    in(n),in(m),in(st),in(ed);
    while(m--)in(x),in(y),in(z),in(w),add_(x,y,z,w);
    EK(st,ed);
    printf("%lld %lld",maxflow,mincost);
}

九：【斯坦纳树】

1.【普通无向图】

【模板】最小斯坦纳树 \(\text{[P6192]}\)

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=503;
int n,m,o,x,y,z,K,ans,pan[N],head[N],dp[N][1024+3];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void SPFA(Re s){
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(dp[x][s]+a[i].w<dp[to=a[i].to][s]){
                dp[to][s]=dp[x][s]+a[i].w;
                if(!pan[to])Q.push(to),pan[to]=1;
            }
    }
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m),in(K);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
    memset(dp,63,sizeof(dp));Re inf=dp[0][0];
    for(Re i=1;i<=K;++i)in(x),dp[x][1<<i-1]=0,ans=x;
    Re V=(1<<K)-1;
    for(Re s=0;s<=V;++s){
        for(Re i=1;i<=n;++i){
            for(Re t=(s-1)&s;t;t=(t-1)&s)
                dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s^t]);
            if(dp[i][s]!=inf)Q.push(i),pan[i]=1;
        }
        SPFA(s);
    }
    printf("%d ",dp[ans][V]);
}

2.【方格图】

游览计划 \(\text{[WC2008] [P4294]}\)

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=12;
int n,m,ct,A[N][N],B[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Steiner_Tree{
    struct PRE{int i,j,s;PRE(Re I=0,Re J=0,Re S=0){i=I,j=J,s=S;}}pre[N][N][1024+3];
    int vis[N][N],dp[N][N][1024+3],wx[4]={-1,0,1,0},wy[4]={0,1,0,-1};
    struct QAQ{int x,y;QAQ(Re X=0,Re Y=0){x=X,y=Y;}};
    queue<QAQ>Q;
    inline void SPFA(Re s){
        while(!Q.empty()){
            QAQ now=Q.front();Q.pop();
            Re x=now.x,y=now.y;vis[x][y]=0;
            for(Re o=0;o<4;++o){
                Re nx=x+wx[o],ny=y+wy[o];
                if(nx<1||nx>n||ny<1||ny>m)continue;
                if(dp[nx][ny][s]>dp[x][y][s]+B[nx][ny]){
                    dp[nx][ny][s]=dp[x][y][s]+B[nx][ny],pre[nx][ny][s]=PRE(x,y,s);
                    if(!vis[nx][ny])Q.push(QAQ(nx,ny)),vis[nx][ny]=1;
                }
            }
        }
    }
    int Ans[N][N];
    inline void dfs(Re i,Re j,Re s){
        Ans[i][j]=1;PRE to=pre[i][j][s];
        if(to.s){
            dfs(to.i,to.j,to.s);
            if(to.i==i&&to.j==j)dfs(to.i,to.j,s^to.s);
        }
    }
    inline void sakura(){
        memset(dp,63,sizeof(dp));
        Re V=(1<<ct)-1,inf=dp[0][0][0];
        for(Re i=1;i<=n;++i)
            for(Re j=1;j<=m;++j)
                if(A[i][j])dp[i][j][1<<A[i][j]-1]=0;
        for(Re s=0;s<=V;++s){
            for(Re i=1;i<=n;++i)
                for(Re j=1;j<=m;++j){
                    for(Re t=(s-1)&s,tmp;t;t=(t-1)&s)
                        if((tmp=dp[i][j][t]+dp[i][j][s^t]-B[i][j])<dp[i][j][s])
                            dp[i][j][s]=tmp,pre[i][j][s]=PRE(i,j,t);
                    if(dp[i][j][s]!=inf)Q.push(QAQ(i,j)),vis[i][j]=1;
                }
            SPFA(s);
        }
        Re ans=2e9,x,y;
        for(Re i=1;i<=n;++i)
            for(Re j=1;j<=m;++j)
                if(A[i][j])ans=dp[x=i][y=j][V];
        printf("%d\n",ans);
        dfs(x,y,V);
        for(Re i=1;i<=n;puts(""),++i)
            for(Re j=1;j<=m;++j)
                putchar(A[i][j]?'x':(Ans[i][j]?'o':'_'));
    }
}T1;
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m);
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j){
            in(B[i][j]);
            if(!B[i][j])A[i][j]=++ct;
        }
    T1.sakura();
}

十：【线段树优化建边】

【模板】\(\text{Legacy}\) \(\text{[CF786B]}\) （\(\text{Dijkstra}\)）

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,x,y,w,l,r,o,op,st,head[N<<3];bool pan[N<<3];LL dis[N<<3];
struct QAQ{int w,to,next;}a[(N<<3)+(N<<2)+N*18*2];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    int O;
    struct QAQ{int in,out;}tr[N<<2];
    inline void build(Re p,Re L,Re R){
        if(L==R){tr[p].in=tr[p].out=L;return;}
        tr[p].in=++O,tr[p].out=++O,add(tr[p].in,tr[p].out,0);
        build(pl,L,mid),build(pr,mid+1,R);
        add(tr[p].in,tr[pl].in,0),add(tr[p].in,tr[pr].in,0);
        add(tr[pl].out,tr[p].out,0),add(tr[pr].out,tr[p].out,0);
    }
    inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w,Re op){
        if(l<=L&&R<=r){
            if(op)add(tr[p].out,x,w);
            else add(x,tr[p].in,w);
            return;
        }
        if(l<=mid)change(pl,L,mid,l,r,x,w,op);
        if(r>mid)change(pr,mid+1,R,l,r,x,w,op);
    }
}TR;
struct QWQ{int x;LL d;inline bool operator<(const QWQ &O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void dijkstra(Re st){
    for(Re i=1;i<=TR.O;++i)dis[i]=inf;
    Q.push((QWQ){st,dis[st]=0});
    while(!Q.empty()){
        Re x=Q.top().x;Q.pop();
        if(pan[x])continue;
        pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(dis[to=a[i].to]>dis[x]+a[i].w)
                Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});
    }
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m),in(st);
    TR.O=n,TR.build(1,1,n);
    while(m--){
        in(op),in(x);
        if(op<2)in(y),in(w),TR.change(1,1,n,y,y,x,w,0);
        else if(op<3)in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,0);
        else in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,1);
    }
    dijkstra(st);
    for(Re i=1;i<=n;++i)printf("%lld ",dis[i]==inf?-1:dis[i]);
}

\(\text{Last chance}\) \(\text{[CF1045A]}\) （\(\text{Dinic}\)）

炸弹 \(\text{[SNOI2017] [P5025]}\)（\(\text{Tarjan}\)）

推荐阅读