图论模板

1.带路径优化的并查集模板:

int Find(int x)
{
  int r=x;
  while(r!=pre[r])
    r=pre[r]; 
  int i=x,j;
  while(pre[i]!=r)//路径优化
  {
    j=pre[i];
    pre[i]=r;
    i=j;
  }
  return r;
}
void mix(int x,int y)
{
  int fx=Find(x),fy=Find(y);
  if(fx!=fy)
  {
    pre[fy]=fx;
  }
}

简化版 

int find(int x){
    return (x == pre[x] ? x : pre[x] = find(pre[x])); 
}

应用题目链接:
HDU P1232 畅享工程
ZOJ Problem Set – 3321 Circle


2.【多源最短路径】Floyed模板:

能收缩所有的距离,还能处理负边权,但是复杂度贼高。O(n3)级别

void floyd()
{
    int i,j,k;
    for (k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                Map[i][j]=min( Map[i][j],Map[i][k]+Map[k][j] );

}

应用题目链接:
vjudge 六度分离


3.【最小生成树】prim算法

const int maxn = 110;
const int INF = maxn*100000;

int w[maxn][maxn];
int d[maxn];
int vis[maxn];
int n;
int ans;

void Prime()
{
    for(int i = 1; i <= n; i++) d[i] = INF;
    d[1] = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++)
    {
        int x, m = INF;
        for(int y = 1; y <= n; y++) if(!vis[y] && d[y] <= m) m = d[x=y];
        vis[x] = 1; ans += d[x];
        for(int y = 1; y <= n; y++) if(!vis[y])
            d[y] = min(d[y], w[x][y]);
    }
}

应用题目链接:

poj1258 – Agri-Net


3.【单源最短路径】Dijkstra算法

(1)当权值为非负时,用Dijkstra。
(2)当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈。
(3)当权值有负值,而且可能存在负圈,则用BellmanFord,能够检测并输出负圈。
(4)SPFA检测负环:当存在一个点入队大于等于V次,则有负环,后面有证明。

1.无法处理负环
2.可以处理单向图与无向图
3.正权图一般都用队列优化的迪杰斯特拉算法解决

一般形式+邻接矩阵://一般不使用邻接矩阵存图

const int INF=0x3f3f3f3f;
const int maxn=1200;

int dist[maxn],g[maxn][maxn],N;
bool vis[maxn];

void dijkstra()
{
  for(int i=1;i<=N;i++)
    dist[i]=(i==1)?0:INF;
  memset(vis,0,sizeof(vis));

  for(int i=1;i<=N;i++)
  {
    int mark=-1,mindis=INF;
    for(int j=1;j<=N;j++)
    {
      if(!vis[j]&&dist[j]<mindis)
      {
        mindis=dist[j];
        mark=j;
      }
    }
    vis[mark]=1;

    for(int j=1;j<=N;j++)
    {
      if(!vis[j])
      {
        dist[j]=min(dist[j],dist[mark]+g[mark][j]);
      }
    }
  }
}

 

邻接表+优先队列优化:

#include <bits/stdc++.h>

using namespace std;
/*
 * 使用优先队列优化Dijkstra算法
 * 复杂度O(ElogE)
 * 注意对vector<Edge>E[MAXN]进行初始化后加边
 */
const int INF=0x3f3f3f3f;
const int MAXN=1000010;
struct qnode
{
    int v;
    int c;
    qnode(int v=0,int c=0):v(v),c(c){}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v,cost;
    Edge(int v=0,int cost=0):v(v),cost(cost){}
};
vector<Edge>E[MAXN];//图
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n,int start)//点的编号从1开始
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    priority_queue<qnode>que;
    while(!que.empty())que.pop();//初始化
    dist[start]=0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
int main()
{
    int n,m;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)E[i].clear();
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            //addedge(v,u,w);无向图
        }
        Dijkstra(n,1);
        //单源最短路,dist[i]为从源点start到i的最短路
    }
    return 0;
}

应用举例:【单源最短路径】dijkstra模板题


4.【单源最短路径】SPFA

#include<iostream>
#include<cstdio>
#include<queue>
#include<queue>
#include<cstring>

using namespace std;

const int MAXN=200010;
//const int INF=0x3f3f3f3f;
const int INF=0x7fffffff;

struct edge{
  int v,cost;
  edge(int _v,int _cost):v(_v),cost(_cost){}
};
vector<edge>E[MAXN];

void add_edge(int u,int v,int w)
{
  E[u].push_back(edge(v,w));
}

bool vis[MAXN];
int cnt[MAXN];
int dist[MAXN];

bool spfa(int start,int n)
{
  memset(vis,false,sizeof(vis));
  for(int i=1;i<=n;i++){
    dist[i]=INF;
  }
  vis[start]=true;
  dist[start]=0;
  queue<int>que;
  while(!que.empty()){
    que.pop();
  }
  que.push(start);
  memset(cnt,0,sizeof(cnt));
  cnt[start]=1;
  while(!que.empty()){
    int u=que.front();
    que.pop();
    vis[u]=false;
    for(int i=0;i<E[u].size();i++){
      int v=E[u][i].v;
      if(dist[v]>dist[u]+E[u][i].cost){
        dist[v]=dist[u]+E[u][i].cost;
        if(!vis[v]){
          vis[v]=true;
          que.push(v);
          if(++cnt[v]>n){
            return false;
          }
        }
      }
    }
  }
  return true;
}

int main()
{
  int n,m,s;
  int T;

  scanf("%d%d%d",&n,&m,&s);
  for(int i=1;i<=n;i++)E[i].clear();
  for(int i=0;i<m;i++)
  {
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    add_edge(u,v,w);
    //addedge(v,u,w);无向图
  }
  spfa(s,n);
  //单源最短路,dist[i]为从源点start到i的最短路
  int ans=0;
  for(int i=1;i<=n;i++)
  {
    cout<<dist[i]<<' ';
  }

  return 0;
}

5.【强连通分量】(太监算法)

讲解

输入:
一个图有向图。
输出:
它每个强连通分量。

 #include<cstdio>
 #include<algorithm>
 #include<string.h>
 using namespace std;
 struct node {
     int v,next;
 }edge[1001];
  int DFN[1001],LOW[1001];
 int stack[1001],heads[1001],visit[1001],cnt,tot,index;
void add(int x,int y)
{
     edge[++cnt].next=heads[x];
     edge[cnt].v = y;
     heads[x]=cnt;
    return ;
 }
 void tarjan(int x)//代表第几个点在处理。递归的是点。
 {
     DFN[x]=LOW[x]=++tot;// 新进点的初始化。
     stack[++index]=x;//进站
     visit[x]=1;//表示在栈里
    for(int i=heads[x];i!=-1;i=edge[i].next)
     {
         if(!DFN[edge[i].v]) {//如果没访问过
            tarjan(edge[i].v);//往下进行延伸,开始递归
             LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,涉及到强连通分量子树最小根的事情。
        }
        else if(visit[edge[i].v ]){  //如果访问过,并且还在栈里。
             LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子/父亲。就是链接对应关系
         }
     }
     if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
    {
         do{
            printf("%d ",stack[index]);
             visit[stack[index]]=0;
             index--;
         }while(x!=stack[index+1]);//出栈,并且输出。
         printf("\n");
     }
     return ;
 }
 int main()
 {
     memset(heads,-1,sizeof(heads));
     int n,m;
     scanf("%d%d",&n,&m);
    int x,y;
     for(int i=1;i<=m;i++)
     {
         scanf("%d%d",&x,&y);
        add(x,y);
     }
    for(int i=1;i<=n;i++)
         if(!DFN[i])  tarjan(i);//当这个点没有访问过,就从此点开始。防止图没走完
    return 0;
 }

 

发表评论

电子邮件地址不会被公开。