图论基本模板总结-白红宇

图论基本模板总结

阅读量：5010 次

发布时间：2019-06-12

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

最短路（vector+Dijkstra优先队列优化）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #define Inf 0x3f3f3f3fconst int maxn=1e5+5;typedef long long ll;using namespace std;struct node{ int pos; int w; node (int x,int y) { pos=x; w=y; } bool friend operator < (node x,node y) { return x.w>y.w; }};vector
                
                 vec[10005];int dis[10005];int vis[10005];int n,m;void init(){ for(int t=1;t<=n;t++) { dis[t]=Inf; } memset(vis,0,sizeof(vis));}void Dijkstra(int s){ priority_queue
                 
                  q; q.push(node(s,0)); dis[s]=0; while(!q.empty()) { node now=q.top(); q.pop(); if(vis[now.pos])continue; vis[now.pos]=1; for(int t=0;t

邻接表+DIjkstra队列优化

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define Inf 0x3f3f3f3fconst int maxn=1e5+5;typedef long long ll;using namespace std;struct edge{ int u,v,w; int next;}Edge[10*maxn];struct node{ int pos,w; node(int x,int y) { pos=x; w=y; } bool friend operator < (node x,node y) { return x.w>y.w; }};int head[1005],dis[1005],vis[1005],cnt=0;void add(int u,int v,int w){ Edge[cnt].u=u; Edge[cnt].v=v; Edge[cnt].w=w; Edge[cnt].next=head[u]; head[u]=cnt++;}void Dijkstra(int s){ dis[s]=0; priority_queue
                
                 q; q.push(node(s,0)); while(!q.empty()) { node now=q.top(); q.pop(); if(vis[now.pos])continue; vis[now.pos]=1; for(int i=head[now.pos];i!=-1;i=Edge[i].next) { if(dis[now.pos]+Edge[i].w
                 
                  >n>>m; int u,v,w; memset(head,-1,sizeof(head)); memset(dis,Inf,sizeof(dis)); for(int t=0;t

SPFA判负环

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #define Inf 0x3f3f3f3fconst int maxn=1e5+5;typedef long long ll;using namespace std;struct Edge{ int u,v,w; int next;}edge[7499];int head[505],vis[505],cnt[505],dis[505],tot;void init(){ memset(head,-1,sizeof(head)); memset(cnt,0,sizeof(cnt)); memset(vis,0,sizeof(vis)); memset(dis,Inf,sizeof(dis));}void add(int u,int v,int w){ edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; return;}int n,m,k; bool SPFA(int s){ dis[s]=0; cnt[s]=1; vis[s]=true; queue
                
                 q; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=false; for(int i=head[now];i!=-1;i=edge[i].next) { if(dis[now]+edge[i].w
                 
                  n) { return true; } if(vis[y]==false) { vis[y]=true; q.push(y); } } } } return false; }int main(){ int T; cin>>T; while(T--) { tot=0; init(); scanf("%d%d%d",&n,&m,&k); int u,v,w; for(int t=0;t

拓扑排序判环

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                const int maxn=1e5+5;typedef long long ll;using namespace std;int du[105];vector
                
                 vec[105];int n,m;bool TPsort(){ queue
                 
                  q; int cnt=0; for(int t=0;t

树的直径

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define Inf 0x3f3f3f3fconst int maxn=1e4+5;typedef long long ll;using namespace std;struct edge{ int to,cost;};vector
               
                 e[maxn];int farthest,ans;void dfs(int x,int pre,int dis){ for(int i=0;i
                
                  ans) { ans = dis; farthest = x; }}int main(){ int i,j; int x,y; edge t; while(scanf("%d%d%d",&x,&y,&t.cost)!=EOF) { t.to = y; e[x].push_back(t); t.to = x; e[y].push_back(t); } ans = 0; dfs(1,-1,0); dfs(farthest,-1,0); printf("%d\n",ans); return 0;}