• 周日. 10 月 6th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

简单图论树论

admin

11 月 28, 2021

1.图的存储与遍历

//链式前向星存储
int cnt,h[maxn];
struct edge{int to,nxt,val;}e[maxm];
void addedge(int u,int v,int val)
{
    e[++cnt]=(edge){v,h[u],val};
    h[u]=cnt;
}
//遍历
for(int i=h[u];i;i=e[i].nxt)
{
    int p=e[i].to;
    //...
}

2.最小生成树

2.1 无向图最小生成树

2.1.1 Kruskal算法

struct edge{int u,v,val;}e[400010];//单纯存边,这不是链式前向星
void init(){for(int i=1;i<=m;i++){fa[i]=i;siz[i]=1;}}
int find(int xx){return fa[xx]==xx?xx:fa[xx]=find(fa[xx]);}
void merge(int xx,int yy)
{
    int fx=find(xx),fy=find(yy);
    if(fx==fy)return;
    if(siz[fx]<siz[fy]){fa[fx]=fy;siz[fy]+=siz[fx];fa[xx]=fy;}
    else{fa[fy]=fx;siz[fx]+=siz[fy];fa[yy]=fx;}
}
bool query(int xx,int yy){return find(xx)==find(yy);}
bool cmp(edge u,edge v){return u.val<v.val;}
int kruskal()
{
    int ans=0;sort(e+1,e+m+1,cmp);init();
    for(int i=1;i<=m;i++)
        if(!query(e[i].u,e[i].v))
        {
            merge(e[i].u,e[i].v);
            ans+=e[i].val;
        }
    return ans;
}

2.1.2 Prim算法(堆优化)

int prim()
{
    int ans=0;
    memset(dis,0x3f,sizeof(dis));
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int u=q.top().second,val=q.top().first;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        ans+=val;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(dis[p]>e[i].val)
            {
                dis[p]=e[i].val;
                q.push(make_pair(dis[p],p));
            }
        }
    }
    return ans;
}

2.2 严格次小生成树

2.3 有向图最小生成树(最小树形图)

3.最短路

3.1 Floyd算法

memset(map,0x3f,sizeof(map));
for(int i=1;i<=n;i++)map[i][i]=0;
for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	    if(map[i][k]<0x3f3f3f3f&&map[k][j]<0x3f3f3f3f&&map[i][j]>map[i][k]+map[k][j])
		map[i][j]=map[i][k]+map[k][j];
for(int i=1;i<=n;i++)
    if(map[i][i]<0)//有负环
    {
	printf("NEGATIVE CYCLE
");
	return 0;
    } 
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
	if(map[i][j]==0x3f3f3f3f)//不连通
	    printf("INF ");
	else
	    printf("%d ",map[i][j]); 
    printf("
");
}

3.2 Dijkstra算法

void dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;q.push(make_pair(0,s));
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(dis[p]>dis[u]+e[i].val)
            {
                dis[p]=dis[u]+e[i].val;
                q.push(make_pair(dis[p],p));
            }
        }
    }
}

3.3 SPFA算法

void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;q.push(s);vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(dis[p]>dis[u]+e[i].val)
            {
                dis[p]=dis[u]+e[i].val;
                if(!vis[p])
                {
                    vis[p]=1;
                    q.push(p);
                }
            }
        }
    }
}

3.4 Johnson算法

bool spfa()
{
    memset(pot,0x7f,sizeof(pot));
    pot[n+1]=0;spfaq.push(n+1);vis[n+1]=1;
    while(!spfaq.empty())
    {
        int u=spfaq.front();spfaq.pop();vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(pot[p]>pot[u]+e[i].val)
            {
                pot[p]=pot[u]+e[i].val;
                if(!vis[p])
                {
                    if(++pathcnt[p]>=n+1)return 1;
                    vis[p]=1;
                    spfaq.push(p);
                }
            }
        }
    }
    return 0;
}
void dijkstra(int s)
{
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;q.push(make_pair(0,s));
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(dis[p]>dis[u]+e[i].val+pot[u]-pot[p])
            {
                dis[p]=dis[u]+e[i].val+pot[u]-pot[p];
                q.push(make_pair(dis[p],p));
            }
        }
    }
}
//main函数里
if(spfa()){printf("-1
");return 0;}
for(int i=1;i<=n;i++)dijkstra(i);

4.负环、差分约束与传递闭包

4.1 对负环的判断

bool spfa()
{
    memset(dis,0x7f,sizeof(dis));
    memset(pathcnt,0,sizeof(pathcnt));
    memset(vis,0,sizeof(vis));
    dis[1]=0;q.push(1);vis[1]=1;pathcnt[1]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(dis[p]>dis[u]+e[i].val)
            {
                dis[p]=dis[u]+e[i].val;
                pathcnt[p]=pathcnt[u]+1;
                if(pathcnt[p]>=n)return 1;
                if(!vis[p])
                {
                    vis[p]=1;
                    q.push(p);
                }
            }
        }
    }
    return 0;
}

4.2 差分约束系统

bool spfa()
{
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;q.push(s);vis[s]=1;pathcnt[s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            if(dis[p]>dis[u]+e[i].val)
            {
                dis[p]=dis[u]+e[i].val;
                pathcnt[p]=pathcnt[u]+1;
                if(pathcnt[p]>=n+1)return 1;
                if(!vis[p])
                {
                    vis[p]=1;
                    q.push(p);
                }
            }
        }
    }
    return 0;
}
//main函数里
n=read();m=read();s=n+1;
for(int i=1;i<=m;i++)
{
    int v=read(),u=read(),val=read();
    addedge(u,v,val);
}
for(int i=1;i<=n;i++)addedge(s,i,0);
if(spfa())printf("NO
");
else for(int i=1;i<=n;i++)printf("%d ",dis[i]);

4.3 传递闭包

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	    if(map[i][k]&&map[k][j])
		map[i][j]=1;

5.LCA

5.1 倍增法

void dfs(int u,int fa)
{
    anc[u][0]=fa;dep[u]=dep[fa]+1;
    for(int i=1;i<=lg2[dep[u]];i++)anc[u][i]=anc[anc[u][i-1]][i-1];
    for(int i=h[u];i;i=e[i].nxt)
    {
        int p=e[i].to;
        if(p!=fa)dfs(p,u);
    }
}
int lca(int u,int v)
{
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]<dep[v])v=anc[v][lg2[dep[v]-dep[u]]];
    if(u==v)return u;
    for(int k=lg2[dep[u]];k>=0;k--)
        if(anc[u][k]!=anc[v][k])
        {
            u=anc[u][k];
            v=anc[v][k];
        }
    return anc[u][0];
}
//预处理
for(int i=2;i<=n;i++)lg2[i]=lg2[i/2]+1;
dep[0]=-1;dfs(s,0);

5.2 RMQ做法

5.3 Tarjan算法

6.Tarjan算法及其应用

6.1 强连通分量及其缩点

6.2 无向图的割点

6.3 无向图的割边(桥)

6.4 边双连通分量及其缩点

6.5 点双联通分量及其缩点

6.6 2-SAT问题

7. 欧拉回路

8. 树的同构

发表回复