【模板】图论-白红宇

【模板】图论

阅读量：5337 次

发布时间：2019-06-15

本文共 14470 字，大约阅读时间需要 48 分钟。

最小生成树：

次小生成树：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct nond{    int x,y,z;}edge[400000];int T,N,M,x,y,z,fa[200000],num,ans[200000];int tot,bns,k,answer=0x7f7f7f7f;int cmp(nond aa,nond bb){    return aa.z
          
           >N>>M;    for(int i=1;i<=M;i++){        cin>>x>>y>>z;        edge[i].x=x;        edge[i].y=y;        edge[i].z=z;    }    sort(edge+1,edge+1+M,cmp);    for(int i=1;i<=N;i++)    fa[i]=i;    for(int i=1;i<=M;i++){        int dx=find(edge[i].x);        int dy=find(edge[i].y);        if(dx!=dy){            fa[dx]=dy;            tot++;            ans[tot]=i;            bns+=edge[i].z;        }        if(tot==N-1)    break;    }    for(int i=1;i<=tot;i++){        k=0;num=0;        for(int j=1;j<=N;j++)    fa[j]=j;        sort(edge+1,edge+1+M,cmp);        for(int j=1;j<=M;j++){            if(j==ans[i])    continue;            int dx=find(edge[j].x);            int dy=find(edge[j].y);            if(dx!=dy){                fa[dx]=dy;                num++;                k+=edge[j].z;            }            if(num==N-1)    break;        }        if(num==N-1&&k!=bns) answer=min(k,answer);    }    cout<

次小生成树

最短路：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 500010using namespace std;deque
           
            que;int n,m,s,vis[MAXN],num[MAXN],dis[MAXN];int tot,to[MAXN],from[MAXN],net[MAXN],cap[MAXN];void add(int u,int v,int w){ to[++tot]=v;net[tot]=from[u];cap[tot]=w;from[u]=tot;}bool spfa(int s){ for(int i=1;i<=n;i++) dis[i]=2147483647; que.push_back(s); vis[s]=1;num[s]++;dis[s]=0; while(!que.empty()){ int now=que.front(); que.pop_front(); vis[now]=0; for(int i=from[now];i;i=net[i]) if(dis[to[i]]>dis[now]+cap[i]){ dis[to[i]]=dis[now]+cap[i]; if(!vis[to[i]]){ if(dis[to[i]]>dis[que.front()]) que.push_back(to[i]); else que.push_front(to[i]); vis[to[i]]=1; num[to[i]]++; if(num[to[i]]>n) return false; } } } return true;}int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); } if(spfa(s)) for(int i=1;i<=n;i++) cout<
            
             <<" ";}

spfa 最短路

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define MAXN 500010using namespace std;struct nond{ int number,dis; bool operator < (nond b) const{ return dis>b.dis; }};int n,m,s,dis[MAXN];int tot,to[MAXN],net[MAXN],from[MAXN],cap[MAXN];void add(int u,int v,int w){ to[++tot]=v;net[tot]=from[u];cap[tot]=w;from[u]=tot;}void dijkstra(int x){ priority_queue
            
             que; for(int i=1;i<=n;i++) dis[i]=2147483647; dis[x]=0; que.push((nond){x,0}); while(!que.empty()){ nond now=que.top(); que.pop(); if(dis[now.number]!=now.dis) continue; for(int i=from[now.number];i;i=net[i]) if(dis[to[i]]>dis[now.number]+cap[i]){ dis[to[i]]=dis[now.number]+cap[i]; que.push((nond){to[i],dis[to[i]]}); } } }int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); } dijkstra(s); for(int i=1;i<=n;i++) cout<
             
              <<" ";}#include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #define MAXN 500010using namespace std;struct nond{ int number,dis; bool operator < (nond b) const{ return dis>b.dis; }};int n,m,s,dis[MAXN];int tot,to[MAXN],net[MAXN],from[MAXN],cap[MAXN];void add(int u,int v,int w){ to[++tot]=v;net[tot]=from[u];cap[tot]=w;from[u]=tot;}void dijkstra(int x){ priority_queue
                    
                     que; for(int i=1;i<=n;i++) dis[i]=2147483647; dis[x]=0; que.push((nond){x,0}); while(!que.empty()){ nond now=que.top(); que.pop(); if(dis[now.number]!=now.dis) continue; for(int i=from[now.number];i;i=net[i]) if(dis[to[i]]>dis[now.number]+cap[i]){ dis[to[i]]=dis[now.number]+cap[i]; que.push((nond){to[i],dis[to[i]]}); } } }int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); } dijkstra(s); for(int i=1;i<=n;i++) cout<
                     
                      <<" ";}

heap优化的dij

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 200010using namespace std;int T,n,m,tot,vist;int vis[MAXN],head[MAXN],dis[MAXN];int to[MAXN*2],cap[MAXN*2],net[MAXN*2];int add(int u,int v,int w){    to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;}int spfa(int now){    vis[now]=1;    for(int i=head[now];i;i=net[i])        if(dis[to[i]]>dis[now]+cap[i]){            dis[to[i]]=dis[now]+cap[i];            if(vis[to[i]]||spfa(to[i])){                vis[to[i]]=0;                return 1;            }        }    vis[now]=0;    return 0;}int main(){    //freopen("a.in","r",stdin);    scanf("%d",&T);    while(T--){        tot=0;vist=0;        memset(to,0,sizeof(to));        memset(cap,0,sizeof(cap));        memset(net,0,sizeof(net));        memset(dis,0,sizeof(dis));        memset(vis,0,sizeof(vis));        memset(head,0,sizeof(head));        scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++){            int x,y,z;            scanf("%d%d%d",&x,&y,&z);            add(x,y,z);            if(z>0) add(y,x,z);        }        for(int i=1;i<=n;i++)            if(spfa(i)){                cout<<"YE5"<

spfa的dfs判负环

（二分图匹配）匈牙利算法：

#include
      
       #include
       
        #include
        
         #include
         
          const int MAXN=1010;using namespace std;int n,m,e,map[MAXN][MAXN];int ans,use[MAXN],girl[MAXN];bool find(int x){    for(int j=1;j<=m;j++)        if(map[x][j]==1&&use[j]==0){            use[j]=1;            if(girl[j]==0||find(girl[j])){                girl[j]=x;                return 1;            }        }    return 0;}int main(){    scanf("%d%d%d",&n,&m,&e);    for(int i=1;i<=e;i++){        int x,y;        scanf("%d%d",&x,&y);         if(x>m||y>m) continue;        map[x][y]=1;    }        for(int i=1;i<=n;i++){        memset(use,0,sizeof(use));        if(find(i))    ans++;    }    printf("%d",ans);}

匈牙利

tarjin：

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 100010using namespace std;int n,m;int sumcol;int tot,tim,top;int col[MAXN];int to[MAXN],net[MAXN],head[MAXN];int low[MAXN],dfn[MAXN],vis[MAXN],stack[MAXN],visstack[MAXN];void add(int u,int v){    to[++tot]=v;net[tot]=head[u];head[u]=tot;}void tarjin(int now){    stack[++top]=now;    low[now]=dfn[now]=++tim;    vis[now]=1;    visstack[now]=1;    for(int i=head[now];i;i=net[i])        if(visstack[to[i]])            low[now]=min(low[now],dfn[to[i]]);        else if(!vis[to[i]]){            tarjin(to[i]);            low[now]=min(low[now],low[to[i]]);        }    if(dfn[now]==low[now]){        sumcol++;        col[now]=sumcol;        while(stack[top]!=now){            col[stack[top]]=sumcol;            visstack[stack[top]]=0;            top--;        }        visstack[now]=0;        top--;    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        int u,v;        scanf("%d%d",&u,&v);        add(u,v);    }    for(int i=1;i<=n;i++)        if(!vis[i])            tarjin(i);    cout<

tarjin求强连通分量的个数

#include#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define MAXN 100010using namespace std;queue
            
             que;map
             
              ma[MAXN];int n,m;int sumcol,ans;int tot,tot1,tim,top;int col[MAXN],into[MAXN];int val[MAXN],cost[MAXN],dis[MAXN];int to[MAXN],net[MAXN],head[MAXN];int to1[MAXN],net1[MAXN],head1[MAXN];int low[MAXN],dfn[MAXN],vis[MAXN],stack[MAXN],visstack[MAXN];void add(int u,int v){ to[++tot]=v;net[tot]=head[u];head[u]=tot;}void add1(int u,int v){ to1[++tot1]=v;net1[tot1]=head1[u];head1[u]=tot1;}void tarjin(int now){ stack[++top]=now; low[now]=dfn[now]=++tim; vis[now]=1; visstack[now]=1; for(int i=head[now];i;i=net[i]) if(visstack[to[i]]) low[now]=min(low[now],dfn[to[i]]); else if(!vis[to[i]]){ tarjin(to[i]); low[now]=min(low[now],low[to[i]]); } if(dfn[now]==low[now]){ sumcol++; col[now]=sumcol; while(stack[top]!=now){ col[stack[top]]=sumcol; visstack[stack[top]]=0; top--; } visstack[now]=0; top--; }}void spfa(int s){ memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); while(!que.empty()) que.pop(); dis[s]=cost[s]; vis[s]=1; que.push(s); while(!que.empty()){ int now=que.front(); que.pop(); vis[now]=0; for(int i=head1[now];i;i=net1[i]) if(dis[to1[i]]

tarjin缩点

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 100010using namespace std;int n,m,ans;int tot=1,tim;int cutdian[MAXN],cutbian[MAXN];int to[MAXN*2],net[MAXN*2],head[MAXN];int low[MAXN],dfn[MAXN],vis[MAXN];void add(int u,int v){    to[++tot]=v;net[tot]=head[u];head[u]=tot;    to[++tot]=u;net[tot]=head[v];head[v]=tot;}void tarjin(int now,int pre){    low[now]=dfn[now]=++tim;    vis[now]=1;    int sum=0;    bool boo=0;    for(int i=head[now];i;i=net[i])        if((i^1)!=pre)            if(!vis[to[i]]){                sum++;                tarjin(to[i],i);                if(low[to[i]]>dfn[now])    cutbian[i/2]=1;                if(low[to[i]]>=dfn[now])    boo=1;                low[now]=min(low[now],low[to[i]]);            }            else    low[now]=min(low[now],dfn[to[i]]);    if(pre==-1){        if(sum>1)    cutdian[now]=1;    }    else if(boo==1)    cutdian[now]=1;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        int u,v;        scanf("%d%d",&u,&v);        add(u,v);    }    for(int i=1;i<=n;i++)        if(!vis[i])            tarjin(i,-1);    for(int i=1;i<=n;i++)        if(cutdian[i])    ans++;    cout<
          
           <

tarjin割边割点

最近公共祖先：

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 500010using namespace std;int n,m,s,tot;int to[MAXN*2],net[MAXN*2],head[MAXN];int dad[MAXN],deep[MAXN],siz[MAXN],top[MAXN];void add(int u,int v){    to[++tot]=v;net[tot]=head[u];head[u]=tot;    to[++tot]=u;net[tot]=head[v];head[v]=tot;}void dfs(int now){    siz[now]=1;    deep[now]=deep[dad[now]]+1;    for(int i=head[now];i;i=net[i])        if(to[i]!=dad[now]){            dad[to[i]]=now;            dfs(to[i]);            siz[now]+=siz[to[i]];        }}void dfs1(int x){    int t=0;    if(!top[x])    top[x]=x;    for(int i=head[x];i;i=net[i])        if(to[i]!=dad[x]&&siz[to[i]]>siz[t])            t=to[i];    if(t){        top[t]=top[x];        dfs1(t);    }    for(int i=head[x];i;i=net[i])        if(to[i]!=dad[x]&&t!=to[i])            dfs1(to[i]);}int lca(int x,int y){    for(;top[x]!=top[y];){        if(deep[top[x]]
          
           deep[y])        swap(x,y);    return x;}int main(){    scanf("%d%d%d",&n,&m,&s);    for(int i=1;i

树链剖分

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 500010using namespace std;int n,m,s,tot;int dad[MAXN][20],deep[MAXN];int to[MAXN*2],net[MAXN*2],head[MAXN];void add(int u,int v){    to[++tot]=v;net[tot]=head[u];head[u]=tot;    to[++tot]=u;net[tot]=head[v];head[v]=tot;}void dfs(int now){    deep[now]=deep[dad[now][0]]+1;    for(int i=0;dad[now][i];i++)        dad[now][i+1]=dad[dad[now][i]][i];    for(int i=head[now];i;i=net[i])        if(!deep[to[i]]){            dad[to[i]][0]=now;            dfs(to[i]);        }}int lca(int x,int y){    if(deep[x]>deep[y])    swap(x,y);     for(int i=18;i>=0;i--)        if(deep[dad[y][i]]>=deep[x])            y=dad[y][i];    if(x==y)    return x;    for(int i=18;i>=0;i--)        if(dad[x][i]!=dad[y][i]){            x=dad[x][i];            y=dad[y][i];        }    return dad[x][0];}int main(){    scanf("%d%d%d",&n,&m,&s);    for(int i=1;i

倍增

网络流：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define NAXN 10001#define MAXN 100001using namespace std;int n,m,s,t;int tot=1,ans;int cur[NAXN],lev[NAXN];int to[MAXN*2],net[MAXN*2],cap[MAXN*2],head[NAXN];void add(int u,int v,int w){    to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;    to[++tot]=u;cap[tot]=0;net[tot]=head[v];head[v]=tot;}bool bfs(){    queue
           
            que; for(int i=1;i<=n;i++){ lev[i]=-1; cur[i]=head[i]; } lev[s]=0; que.push(s); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=head[now];i;i=net[i]) if(lev[to[i]]==-1&&cap[i]>0){ lev[to[i]]=lev[now]+1; que.push(to[i]); if(to[i]==t) return true; } } return false;}int dinic(int now,int flow){ if(now==t) return flow; int rest=0,detal; for(int & i=cur[now];i;i=net[i]) if(cap[i]>0&&lev[to[i]]==lev[now]+1){ detal=dinic(to[i],min(flow-rest,cap[i])); if(detal){ rest+=detal; cap[i]-=detal; cap[i^1]+=detal; if(rest==flow) break; } } if(rest!=flow) lev[now]=-1; return rest;}int main(){ cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } while(bfs()) ans+=dinic(s,0x7fffffff); cout<

网络流最大流

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define NAXN 10001#define MAXN 100001using namespace std;int n,m,s,t;int tot=1,ans;int cur[NAXN],lev[NAXN];int to[MAXN*2],net[MAXN*2],cap[MAXN*2],head[NAXN];void add(int u,int v,int w){    to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;    to[++tot]=u;cap[tot]=0;net[tot]=head[v];head[v]=tot;}bool bfs(){    queue
           
            que; for(int i=1;i<=n;i++){ lev[i]=-1; cur[i]=head[i]; } lev[s]=0; que.push(s); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=head[now];i;i=net[i]) if(lev[to[i]]==-1&&cap[i]>0){ lev[to[i]]=lev[now]+1; que.push(to[i]); if(to[i]==t) return true; } } return false;}int dinic(int now,int flow){ if(now==t) return flow; int rest=0,detal; for(int & i=cur[now];i;i=net[i]) if(cap[i]>0&&lev[to[i]]==lev[now]+1){ detal=dinic(to[i],min(flow-rest,cap[i])); if(detal){ rest+=detal; cap[i]-=detal; cap[i^1]+=detal; if(rest==flow) break; } } if(rest!=flow) lev[now]=-1; return rest;}int main(){ cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } while(bfs()) ans+=dinic(s,0x7fffffff); cout<