长乐7.15集训

又是艰难的一天,生活不易,淇淇叹气

 


1.并查集:https://www.bilibili.com/video/BV13t411v7Fs?from=search&seid=18163582992417912843

模板:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

const int N=10005;

int n,m;
int fa[N];

void Init()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
}

int Find(int x)
{
    if(fa[x]!=x) return fa[x]=Find(fa[x]);
    return fa[x];
}

void Merge(int x,int y)
{
    int x_root=Find(x);
    int y_root=Find(y);
    if(x_root!=y_root)
        fa[x_root]=y_root;
}

int main()
{
    cin>>n>>m;
    Init();
    for(int i=1;i<=m;i++)
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1) Merge(x,y);
        if(z==2)
        {
            if(Find(x)==Find(y)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }

    return 0;
}

 


2.最小生成树:https://www.bilibili.com/video/BV1Eb41177d1?from=search&seid=12623132578193160421

模板:

Prim:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;

const int N=1005;
const int INF=1e9;

int n,m;
int f[N][N];
int dis[N];
int vst[N];
int ans;

void Init()
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=INF;
        for(int j=1;j<=n;j++)
        {
            if(i!=j) f[i][j]=INF;
        }
    }
}

void Prim(int x)
{
    ans=0;
    int minn,k;
    dis[x]=0;
    for(int i=1;i<=n;i++)
    {
        minn=INF;
        for(int j=1;j<=n;j++)
        {
            if(vst[j]==0 && minn>dis[j])
            {
                minn=dis[j];
                k=j;
            }
        }
        ans+=dis[k];
        vst[k]=1;
        for(int j=1;j<=n;j++)
        {
            if(vst[j]==0 && dis[j]>f[k][j])
            {
                dis[j]=f[k][j];
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    Init();
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        f[u][v]=f[v][u]=c;
    }
    Prim(1);
    cout<<ans;

    return 0;
}

 

Kruskal :


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;

const int N=10005;

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

struct node
{
    int u;
    int v;
    int w;
}e[N*2];

bool cmp(node x,node y)
{
    return x.w<y.w;
}

int Find_root(int x)
{
    if(fa[x]!=x) return fa[x]=Find_root(fa[x]);
    return fa[x];
}

bool Merge(int x,int y)
{
    int x_root=Find_root(x);
    int y_root=Find_root(y);
    if(x_root!=y_root)//判断 且 合并集合
    {
        fa[x_root]=y_root;
        return 1;
    }
    return 0;
}

void Kruskal()
{
    ans=0;
    int k=0;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        if(Merge(e[i].u,e[i].v))
        {
            ans+=e[i].w;
            k++;
        }
        if(k==n-1) break;
    }
    if(k==n-1) cout<<ans;
    else cout<<-1;
   
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1,cmp);
    Kruskal();

    return 0;
}

 


3.繁忙城市:http://noip.ybtoj.com.cn/contest/32/problem/1

题解:纯Prim或纯Kruskal都可

 


4.新的开始:http://noip.ybtoj.com.cn/contest/32/problem/2

题解:设置虚拟节点(即0号节点)为超级电源,在矿井上建立发电站相当于让它与0号节点连边。

 


5.公路建设:http://noip.ybtoj.com.cn/contest/32/problem/3

题解:貌似写Kruskal会好一点,可是我写的Prim,样例过了,ojwa,不想改了

 


6.连接云朵:http://noip.ybtoj.com.cn/contest/33/problem/1

题解:用Kruskal,当子集等于k的时候就是最小值了

 


The end.