清北学堂（2019 5 2） part 5

今天讲图论，顺便搞一搞之前没弄完的前向星dij

1.图的基本概念（课件原话）：

　　G （图）= (V（点）; E（边）)
　　一般来说，图的存储难度主要在记录边的信息
　　无向图的存储中，只需要将一条无向边拆成两条即可
　　邻接矩阵：用一个二维数组 edg[N][N] 表示
　　edg[i][j] 就对应由 i 到 j 的边信息
　　edg[i][j] 可以记录 Bool，也可以记录边权
　　缺点：如果有重边有时候不好处理
　　空间复杂度 O(V²)
　　点度（出边入边条数）等额外信息也是很好维护的
　　模板（传说中的链式前向星/链式存图）：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,m,s;

struct Ed{

    int next,dis,to;

}ed[N];

int ed_num;

int tail[N];

inline void add(int from,int to,int dis){

    ed_num++;

    ed[ed_num].dis=dis;

    ed[ed_num].to=to;

    ed[ed_num].next=tail[from];

    tail[from]=ed_num;

}

int main(){

    scanf("%d%d%d",&n,&m,&s);

    for(int i=;i<=m;i++){

        int a,b,c;

        add(a,b,c);

    }

    //use it

    for(int i=tail[s];i;i=ed[i].next){

        //bla bla bla...

    }

    printf("What ever it takes\n");

    return ;

}

2.vector

　　用于灵活储存一定范围内（指不会爆栈）数据的变长数组

　　队列好像就是这么存的，然而这个东西很慢...

最小生成树：

3.kruskal（前置知识：并查集）：

　　将每条边排序，按从小到大加入生成树，并将两端点合并作同一并查集，

　　如果边的两端点再加入此边之前已属于同一集合，说明其已经连通，无需加入这一条边

　　如果当前边数已经为n-1，则跳出循环，已经找到目标

#include<bits/stdc++.h>

using namespace std;

int n,m;

int fa[];

inline int father(int t){

    if(fa[t]!=t) fa[t]=father(fa[t]);

    return fa[t];

}

inline void u(int l,int r){

    int fl=father(l);

    int fr=father(r);

    if(fl!=fr) fa[fl]=fr;

}

struct ed{

    int len;

    int begin,end;

}dis[];

inline bool cmp(ed a,ed b){

    return a.len<b.len;

}

int sum;

int num;

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        fa[i]=i;

    for(int i=;i<=m;i++){

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        dis[i].begin=x;

        dis[i].end=y;

        dis[i].len=z;

    }sort(dis+,dis++m,cmp);

    for(int i=;i<=m;i++){

        if(father(dis[i].begin)!=father(dis[i].end)){

            u(dis[i].begin,dis[i].end);

            sum+=dis[i].len;

            num++;

        }

        if(num==n-){

            cout<<sum<<endl;

            return ;

        }

    }

    cout<<"orz";

    return ;

}

4.kosaraju（偷一波baidu）

　　对原图G进行深度优先遍历，记录每个节点的离开时间num[i]

　　选择具有最晚离开时间的顶点，对反图GT（由G的反向边组成）进行遍历，删除能够遍历到的顶点

　　这些顶点构成一个强连通分量（好像是互相连通的意思）

　　如果还有顶点没有删除，继续步骤2，否则算法结束

5.prim

　　思想：一开始有n个连通块，从起点开始，每次找距离最短的连通块连到一起

　　代码：咕咕咕

总的来说，最小生成树还是用kruskal吧...

最短路问题（共四个,真正意义上是3个）：

给一个有向图，求s到e的最短距离（距离：两点之间边的边权和）

6.松弛操作——最短路算法的本质

　　dis[i][j]<=dis[i][k]+dis[k][j]

7.floyd（之前打的一直是错的）：

　　三层循环找上面式子的i（起点），j（终点），k（中间点）

　　代码（邻接矩阵）：

#include <bits/stdc++.h>

using namespace std;

const int N=;

const int inf=<<;

int d[N][N],n,m;

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++) d[i][j]=inf;

    for(int u,v,w,i=;i<=m;i++)

        cin>>u>>v>>w,d[u][v]=min(d[u][v],w);

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

    printf("并没有输出\n");

    return ;

}

　　要点：

　　1.先要枚举k，不然就是错的

　　2.把最大边初始化为inf（infinite），即为极大（无穷），不然你min怎么取...（全是0）

　　3.主要思路是在k=t循环结束时，dis[i][j]只经过1,2...t，此时dis[i][j]为真实值

　　4.负权环（一个可以跑死SPFA的东西）：

　　Floyd跑完以后判断下有没有负边权就好，Floyd能处理，但SPFA会凉，

　　具体解决办法就是加一个计数变量，如果处理次数大于预期最大次数，就输出无解或关闭程序

单源最短路问题：

8.Bellman-Ford：

　　枚举每一条边（e（u，v，w））并松弛d（v）=min{d（v），d（u）+w}

　　松弛n次即可，可以加一个优化，

　　添加bool变量判断有没有进行松弛，没有就不用再进行该层循环了

9.SPFA：

　　把需要松弛的边用queue存储，等松弛时拿出操作，代码：

#include<bits/stdc++.h>

using namespace std;

const int inf=;

bool vis[];

int dis[];

int tail[];

struct Ed{

    int next,to,dis;

}ed[];

int m,n,s;

int num_edge;

inline void join(int from,int to,int dis){

    num_edge++;

    ed[num_edge].dis=dis;

    ed[num_edge].to=to;

    ed[num_edge].next=tail[from];

    tail[from]=num_edge;

}

queue<int> q;

int main(){

    scanf("%d%d%d",&n,&m,&s);

    for(int i=;i<=m;i++)

        dis[i]=inf;

    vis[s]=;

    dis[s]=;

    for(int i=;i<=m;i++){

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        join(x,y,z);

    }

    q.push(s);

    while(!q.empty()){

        int now=q.front();

        q.pop();

        vis[now]=;

        for(int i=tail[now];i;i=ed[i].next){

            int end=ed[i].to;

            if(dis[end]>dis[now]+ed[i].dis){

                dis[end]=dis[now]+ed[i].dis;

                if(!vis[end]){

                    q.push(end);

                    vis[end]=;

                }

            }

        }

    }

    for(int i=;i<=n;i++){

        printf("%d ",dis[i]);

    }

    return ;

}

　　优化（上面提到过）：

　　记录每个点加入queue次数，如果大于n-1次，则这个点可能已经在负权环里面无限快乐了

　　SPFA跑稀疏图很快，跑网格图就非常慢了

10.dijkstra

　　前向星版本完成辣！

　　代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int inf=;

struct Ed{

    int to,dis,next;

}ed[];

int tail[];

int ed_num;

inline void add(int from,int to,int dis){

    ed_num++;

    ed[ed_num].dis=dis;

    ed[ed_num].to=to;

    ed[ed_num].next=tail[from];

    tail[from]=ed_num;

}

int dis[];

bool vis[];

int n,m,s;

int main(){

    scanf("%d%d%d",&n,&m,&s);

    for(int i=;i<=n;i++)

        dis[i]=inf;

    dis[s]=;

    vis[s]=;

    for(int i=;i<=m;i++){

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    for(int i=tail[s];i;i=ed[i].next)

        dis[ed[i].to]=ed[i].dis;

    for(int i=;i<=n;i++){

        int now=inf;

        int k=;

        for(int j=;j<=n;j++)

            if((!vis[j])&&(now>dis[j])){

                now=dis[j];

                k=j;

            }

        if(k==) break;

        vis[k]=;

        for(int j=tail[k];j;j=ed[j].next)

            if(dis[ed[j].to]>dis[k]+ed[j].dis)

                dis[ed[j].to]=dis[k]+ed[j].dis;

    }

    for(int i=;i<=n;i++) printf("%d ",dis[i]);

    return ;

}

　　我开心地交了上去٩(๑>◡<๑)۶

　　.......

11.DAG有向无环图与拓扑排序

　　即找一个按顺序遍历所有节点的顺序，显然答案不唯一

　　思想类似于完成一些任务，而某些任务有其前置任务

　　思路：

　　先将所有入度为0的点入队，再依次广搜，把入队的点删除，将它到达的点入度-1

　　依次重复步骤，直到队列为空

　　老师代码（懒得自己敲了）：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + ;

const int inf =  << ;

struct edge{

    int u, v;

};

vector<edge> edg[N];

int n, m, outdeg[N], ans[N];

queue<int> Queue;

void add(int u, int v)

{

    edg[u].push_back((edge){u, v});

}

int main()

{

    cin >> n >> m;

    for (int u, v, i = ; i <= m; i++)

        cin >> u >> v, add(v, u), outdeg[u]++;

    for (int i = ; i <= n; i++)

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

struct edge {

    int u, v, w;

}edg[maxn];

int n, m, p[maxn], Q, dep[maxn];

vector<edge> adj[maxn]; // edges in MST

bool cmp(edge a, edge b)

    {return a.w < b.w;}

int findp(int t)

    {return p[t] ? p[t] = findp(p[t]) : t;}

bool merge(int u, int v)

{

    u = findp(u); v = findp(v);

    if (u == v) return false;

    p[u] = v; return true;

}

int anc[maxn][], maxw[maxn][];

void dfs(int u)

{

    for (int j = ; j < ; j++)

        anc[u][j] = anc[anc[u][j - ]][j - ],

        maxw[u][j] = max(maxw[u][j - ], maxw[anc[u][j - ]][j - ]);

    for (unsigned i = ; i < adj[u].size(); ++i)

    {

        int v = adj[u][i].v, w = adj[u][i].w;

        if (v != anc[u][])

            dep[v] = dep[u] + , anc[v][] = u, maxw[v][] = w, dfs(v);

    }

}

int solve(int u, int v)

{

    int res = ;

    if (dep[u] < dep[v]) swap(u, v);

    for (int d = dep[u] - dep[v], j = ; d ; d >>= , ++j)

        if (d & ) res = max(res, maxw[u][j]), u = anc[u][j];

        //adjust u & v to the same depth

    if (u == v)    return res; //u & v meet now

    for (int j = ; j >= ; j--)

        if (anc[u][j] != anc[v][j]) // if anc[u][j] & anc[v][j] dont meet together, then jump u & v

            res = max(res, maxw[u][j]),

            res = max(res, maxw[v][j]),

            u = anc[u][j], v = anc[v][j];

    //now u & v 's lca must be their parent now, in an easy word, it's anc[u][0] or anc[v][0]

    res = max(res, maxw[u][]);

    res = max(res, maxw[v][]);

    u = anc[u][]; v = anc[v][];

    return res;

}

int main()

{

    cin >> n >> m >> Q;

    for (int i = , u, v, w; i <= m; i++)

        cin >> u >> v >> w, edg[i] = (edge){u, v, w};

    sort(edg + , edg + m + , cmp);

    for (int i = , u, v; i <= m; i++)

        if (merge(u = edg[i].u, v = edg[i].v))

            adj[u].push_back(edg[i]),

            adj[v].push_back((edge){v, u, edg[i].w});

    dfs();

    for (int u, v, i = ; i <= Q; i++)

        cin >> u >> v, cout << solve(u, v) << endl;

}

if (outdeg[i] == ) Queue.push(i);

    for (int i = ; i <= n; i++)

    {

        if (Queue.empty())

            {printf("Not DAG"); return ;}

        int u = Queue.front(); Queue.pop(); ans[n - i + ] = u;

        for (int e = ; e < edg[u].size(); e++)

        {

            int v = edg[u][e].v;

            if (--outdeg[v] == ) Queue.push(v);

        }

    }

}

11.lca（最近公共祖先）

　　思路，先将二者跳到同一深度，再将x和y以尽量远的高度向上跳，直到父节点唯一

　　代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

struct edge {

    int u, v, w;

}edg[maxn];

int n, m, p[maxn], Q, dep[maxn];

vector<edge> adj[maxn]; // edges in MST

bool cmp(edge a, edge b)

    {return a.w < b.w;}

int findp(int t)

    {return p[t] ? p[t] = findp(p[t]) : t;}

bool merge(int u, int v)

{

    u = findp(u); v = findp(v);

    if (u == v) return false;

    p[u] = v; return true;

}

int anc[maxn][], maxw[maxn][];

void dfs(int u)

{

    for (int j = ; j < ; j++)

        anc[u][j] = anc[anc[u][j - ]][j - ],

        maxw[u][j] = max(maxw[u][j - ], maxw[anc[u][j - ]][j - ]);

    for (unsigned i = ; i < adj[u].size(); ++i)

    {

        int v = adj[u][i].v, w = adj[u][i].w;

        if (v != anc[u][])

            dep[v] = dep[u] + , anc[v][] = u, maxw[v][] = w, dfs(v);

    }

}

int solve(int u, int v)

{

    int res = ;

    if (dep[u] < dep[v]) swap(u, v);

    for (int d = dep[u] - dep[v], j = ; d ; d >>= , ++j)

        if (d & ) res = max(res, maxw[u][j]), u = anc[u][j];

        //adjust u & v to the same depth

    if (u == v)    return res; //u & v meet now

    for (int j = ; j >= ; j--)

        if (anc[u][j] != anc[v][j]) // if anc[u][j] & anc[v][j] dont meet together, then jump u & v

            res = max(res, maxw[u][j]),

            res = max(res, maxw[v][j]),

            u = anc[u][j], v = anc[v][j];

    //now u & v 's lca must be their parent now, in an easy word, it's anc[u][0] or anc[v][0]

    res = max(res, maxw[u][]);

    res = max(res, maxw[v][]);

    u = anc[u][]; v = anc[v][];

    return res;

}

int main()

{

    cin >> n >> m >> Q;

    for (int i = , u, v, w; i <= m; i++)

        cin >> u >> v >> w, edg[i] = (edge){u, v, w};

    sort(edg + , edg + m + , cmp);

    for (int i = , u, v; i <= m; i++)

        if (merge(u = edg[i].u, v = edg[i].v))

            adj[u].push_back(edg[i]),

            adj[v].push_back((edge){v, u, edg[i].w});

    dfs();

    for (int u, v, i = ; i <= Q; i++)

        cin >> u >> v, cout << solve(u, v) << endl;

}

巴特西

清北学堂（2019 5 2） part 5

最新文章

热门文章