7-1 图论#

树的直径#

我看网上的博客。一般树的直径可以跑一遍深度，然后从深度最大的开始跑一下最远的，这个方法还可以把树的直径上的点拿出来

1
ve<ve<int>>ed(n+1);
2
ve<int>dis(n+1);
3
int ls,rs,maxl,maxr;
4
void dfs1(int u,int la)
5
{
6
    dep[u]=dep[la]+1;
7
    if(maxl<dep[u])
8
    {
9
        maxl=dep[u];
10
        ls=u;
11
    }
12

13

14
    for(auto v:ed[u])
15
    {
16
        if(v==la) continue;
17
        dfs1(v,u);
18
    }
19
}
20

21
void dfs2(int u,int la)
22
{
23
    dis[u]=dis[la]+1;
24
    if(maxr<dis[u])
25
    {
26
        maxr=dis[u];
27
        rs=u;
28
    }
29

30
    for(auto v:ed[u])
31
    {
32
        if(v==la) continue;
33
        fa[v]=u;//处理前缀
34
        dfs2(v,u);
35
    }
36
}
37

38
//ls,rs 就是树的直径的两个端点
39
ls,rs
40

41

42
//拿出树的直径上的端点
43
ve<int>f;
44
while(rs!=ls)
45
{
46
    f.push_back(rs);
47
    rs=fa[rs];
48
}
49
f.push_back(ls);

树的中心#

树的重心#

单源最短路(djstka)#

1
struct node
2
{
3
    int x,ds;
4
};
5
struct cmp
6
{
7
    bool operater()(node a,node b)
8
    {
9
        return a.ds>b.ds;//当a.ds>b.ds时交换，这个时小顶堆
10
    }
11
};
12

13
ve<ve<int>>ed[N];
14
ve<int>st[N];
15

16
void djs()
17
{
18
    priority_queue<node,ve<node>,cmp>pq;
19
    pq.push({});
20
    while(pq.size())
21
    {
22
        auto [u,ds]=pq.top();pq.pop();
23
        if(st[u]) continue;
24
        st[u]=1;
25
        for(auto [v,w]:ed[u])
26
        {
27
            if(dis[v]>dis[u]+w)
28
            {
29
                dis[v]=dis[u]+w;
30
                pq.push({v,dis[v]});
31
            }
32
        }
33
    }
34
}

分层最短路也是常用的，分层图最短路

多源最短路#

floyd （O(n^3) 三层暴力跑最短路）

1
#include <bits/stdc++.h>
2
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
3
#define fix(x) fixed<<setprecision(x)
4
#define int long long
5
using namespace std;
6
using ll = long long;
7
template<class T>
8
using ve = vector<T>;
9
using pii = pair<int, int>;
10
const int N = 1e6 + 10;
11
const int mod = 1e9 + 7;
12

13
int n,m,q;
14
int a[N][N];
15

16

17
void solve()
18
{
19
    cin>>n>>m>>q;
20
    for(int i=1;i<=n;i++)
21
    {
22
        for(int j=1;j<=n;j++)
23
        {
24
            if(i==j) a[i][j]=0;
25
            else a[i][j]=1e18;
26
        }
27
    }
28
    for(int i=1;i<=m;i++)
29
    {
30
        int u,v,w;cin>>u>>v>>w;
31
        a[u][v]=min(a[u][v],w);
32
    }
33

34
    for(int k=1;k<=n;k++)
35
    {//k是分割点
36
        for(int i=1;i<=n;i++)
37
        {
38
            for(int j=1;j<=n;j++)
39
            {
40
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
41
            }
42
        }
43
    }
44

45
    while(q--)
46
    {
47
        int x,y;cin>>x>>y;
48
        if(a[x][y]>=1e9/2 )cout<<"impossible"<<'\n';
49
        else cout<<a[x][y]<<'\n';
50
    }
51

52
}
53

54
signed main()
55
{
56
    IOS;
57
    int _ = 1; //cin >> _;
58
    while (_--) solve();
59
    return 0;
60
}

最小生成树(并查集)#

1
/*
2

3

4
克鲁斯卡尔算法
5

6
是并查集维护的，把边存一下，然后每次拿最小的边权，
7
如果不会形成环加上，反之舍弃此边。
8

9

10
*/
11

12
#include <bits/stdc++.h>
13
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
14
#define fix(x) fixed<<setprecision(x)
15
#define int long long
16
using namespace std;
17
using ll = long long;
18
template<class T>
19
using ve = vector<T>;
20
using pii = pair<int, int>;
21
const int N = 1e6 + 10;
22
const int mod = 1e9 + 7;
23

24
struct node
25
{
26
    int a,b,c;
27
};
28
bool cmp(node x,node y)
29
{
30
    return x.c<y.c;
31
}
32

33
int f[N];
34
int find(int x)
35
{
36
    if(f[x]!=x) f[x]=find(f[x]);
37
    return f[x];
38
}
39
void solve()
40
{
41
    int n,m;cin>>n>>m;
42
    for(int i=1;i<=n;i++) f[i]=i;
43
    ve<node>a;
44
    for(int i=1;i<=m;i++)
45
    {
46
        int u,v,w;cin>>u>>v>>w;
47
        a.push_back({u,v,w});
48
    }
49
    sort(a.begin(),a.end(),cmp);
50
    int ans=0;
51
    int res=0;
52
    for(int i=0;i<a.size();i++)
53
    {
54
        auto [u,v,w]=a[i];
55
        u=find(u),v=find(v);
56
        if(u==v) continue;
57
        f[u]=v;
58
        ans+=w;
59
        res++;
60
    }
61
    if(res!=n-1) cout<<"orz\n";
62
    else cout<<ans<<'\n';
63
}
64

65
signed main()
66
{
67
    IOS;
68
    int _ = 1; //cin >> _;
69
    while (_--) solve();
70
    return 0;
71
}

基环树#

基环树是n个节点，n条边的数据结构，基环树有一个环

有向边的基环树，指向环的是内向树，反之是外向树

dfs找环

1
set<int>se;
2
void dfs_c(int u,int la)
3
{
4
    //st标记是否遍历,ins表示是否在栈中//
5
    st[u]=ins[u]=true;
6
    for(auto v:ed[u])
7
    {
8
        if(st[v]) continue;
9

10

11
        fa[v]=u;
12
        dfs_c(v,u);
13
        if(ins[v]) //在栈中，这个感觉是找即环树的一种方式
14
        {//找到环
15

16

17
        //拿出环
18
            int id=u;
19
            se.insert(v);
20
            while(id!=v)
21
            {
22
                se.insert(id);
23
                id=fa[id];
24
            }
25
            break;
26
        //
27
        }
28
    }
29
    ins[u]=false;//
30
}