图论模板

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;
  }
}

简化find函数版 

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

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;
 }

6.求最大图,最大完全联通子图

#include<cstdio>  
#include<cstring>  
#define N 1010  
/*
最大团 = 补图G的最大独立集数
———>最大独立集数 = 补图G'最大团
*/
//最大团模板  
bool a[N][N];//a为图的邻接表(从1开始)   
int ans, cnt[N], group[N], n, m, vis[N];//ans表示最大团,cnt[N]表示当前最大团的节点数,group[N]用以寻找一个最大团集合   
bool dfs(int u, int pos)//u为当从前顶点开始深搜,pos为深搜深度(即当前深搜树所在第几层的位置)   
{
	int i, j;
	for (i = u + 1; i <= n; i++)//按递增顺序枚举顶点   
	{
		if (cnt[i] + pos <= ans) return 0;//剪枝   
		if (a[u][i])
		{
			// 与目前团中元素比较,取 Non-N(i)   
			for (j = 0; j < pos; j++) if (!a[i][vis[j]]) break;
			if (j == pos)
			{     // 若为空,则皆与 i 相邻,则此时将i加入到 最大团中   
				vis[pos] = i;//深搜层次也就是最大团的顶点数目,vis[pos] = i表示当前第pos小的最大团元素为i(因为是按增顺序枚举顶点 )   
				if (dfs(i, pos + 1)) return 1;
			}
		}
	}
	if (pos > ans)
	{
		for (i = 0; i < pos; i++)
			group[i] = vis[i]; // 更新最大团元素   
		ans = pos;
		return 1;
	}
	return 0;
}
void maxclique()//求最大团   
{
	ans = -1;
	for (int i = n; i > 0; i--)
	{
		vis[0] = i;
		dfs(i, 1);
		cnt[i] = ans;
	}
}
int main()
{
	//freopen("D:\in.txt","r",stdin);  
	int T;
	//scanf("%d",&T);  
	while (~scanf("%d", &n))
	{
		if (n == 0) break;
		//scanf("%d%d",&n,&m );  
		int x, y;
		memset(a, 0, sizeof(a));
		/*for(int i = 0; i < m; i++)
		{
			scanf("%d%d",&x,&y);
			a[x][y] = a[y][x] = 1;
		}*/
		//相邻顶点间有边相连,模型转换成求 无向图 最大独立集。   
		//要求原图的最大独立集,转化为求原图的补图的最大团(最大团顶点数量 = 补图的最大独立集)      
		for (int i = 1; i <= n; i++)//求原图的补图   
			for (int j = 1; j <= n; j++)
				scanf("%d", &a[i][j]);
		maxclique();//求最大团   
		if (ans < 0) ans = 0;//ans表示最大团  
		printf("%d\n", ans);
		/*for(int i = 0; i < ans; i++)
			printf( i == 0 ? "%d" : " %d", group[i]);//group[N]用以寻找一个最大团集合
		if( ans > 0 ) puts("");*/
	}
}

7.tarjan求割点

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;

/*
*  求 无向图的割点和桥
*  可以找出割点和桥,求删掉每个点后增加的连通块。
*  需要注意重边的处理,可以先用矩阵存,再转邻接表,或者进行判重
*/
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge
{
    int to,next;
    bool cut;//是否为桥的标记
}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;

void addedge(int u,int v)
{
    edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;
    head[u] = tot++;
}


void Tarjan(int u,int pre)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    for(int i = head[u];i != -1;i = edge[i].next)
    {
        v = edge[i].to;
        if(v == pre)continue;
        if( !DFN[v] )
        {
            son++;
            Tarjan(v,u);
            if(Low[u] > Low[v])Low[u] = Low[v];
            //桥
            //一条无向边(u,v)是桥,当且仅当(u,v)为树枝边,且满足DFS(u)<Low(v)。
            if(Low[v] > DFN[u])
            {
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
            //割点
            //一个顶点u是割点,当且仅当满足(1)或(2) (1) u为树根,且u有多于一个子树。
            //(2) u不为树根,且满足存在(u,v)为树枝边(或称父子边,
            //即u为v在搜索树中的父亲),使得DFS(u)<=Low(v)
            if(u != pre && Low[v] >= DFN[u])//不是树根
            {
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if( Low[u] > DFN[v])
             Low[u] = DFN[v];
    }
    //树根,分支数大于1
    if(u == pre && son > 1)cut[u] = true;
    if(u == pre)add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}

void solve(int N)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(add_block,0,sizeof(add_block));
    memset(cut,false,sizeof(cut));
    Index = top = 0;
    bridge = 0;
    for(int i = 1;i <= N;i++)
       if(!DFN[i])
          Tarjan(i,i);
    int ans = 0;
    for(int i = 1;i <= N;i++)
       if(cut[i])
          ans++;
    printf("%d\n",ans);
}
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
int g[110][110];
char buf[1010];
int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        gets(buf);
        memset(g,0,sizeof(g));
        while(gets(buf))
        {
            if(strcmp(buf,"0")==0)break;
            char *p = strtok(buf," ");
            int u;
            sscanf(p,"%d",&u);
            p = strtok(NULL," ");
            int v;
            while(p)
            {
                sscanf(p,"%d",&v);
                p = strtok(NULL," ");
                g[u][v]=g[v][u]=1;
            }
        }
        init();
        for(int i = 1;i <= n;i++)
           for(int j = i+1;j <= n;j++)
              if(g[i][j])
              {
                  addedge(i,j);
                  addedge(j,i);
              }
        solve(n);
    }
    return 0;
}

 

发表评论

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