长乐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.

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

[BZOJ 3624] [APIO 2008] 免费道路

并查集。

题意:求把 N 个点用 N-1 条边连成一棵树,且其中恰有 K 条边为 0 边的一种方案。

第一反应:先连 0 边再连 1 边。

但可能会有这么一种情况:所有的 1 边都连上之后仍然整个图仍然是不联通的。这意味着有一些 0 边是必选的。但如果像上面那样直接做的话可能选不到这些边,从而得不出答案。

于是可以这样做:

先把所有 1 边端点合并,然后接着枚举 0 边,若两顶点不在同一集合中,则把这条边端点所在集合合并,并加入答案中。

接着把并查集重置成只有答案集合中的边的情况,加入能加的 0 边直到答案中的 0 边数量达到 K。最后加入 1 边。

这题还要判断方案是否存在,判断方法为 1. 选取的 0 边边数恰为 K。 2. 选取的总边数为 N-1

代码如下(BZOJ 有点诡异,endl 交上去会 RTE,而 '\n' 就没问题):

继续阅读[BZOJ 3624] [APIO 2008] 免费道路

[BZOJ 4031] [HEOI 2015] 小Z的房间

Kirchhoff's theorem or Kirchhoff's matrix tree theorem

  1. G的度数矩阵DG是一个n*n的矩阵,并且满足:当i≠j时,Di,j=0;当i=j时,Di,j等于Vi的度数。
  2. G的邻接矩阵AG也是一个n*n的矩阵,并且满足:如果ViVj之间有边直接相连,则Ai,j=1,否则为0。

定义G的 Kirchhoff 矩阵CGCG=DGAG

Matrix-Tree 定理:G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 CG任何一个n-1阶主子式(去掉第行第i列的新矩阵)的行列式的绝对值。

运用高斯消元计算行列式绝对值。高斯消元过程中除法运用辗转相消实现。

Reference:

https://www.cnblogs.com/wuyuhan/p/5238652.html

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/u010182633/article/details/45225179

代码如下:

继续阅读[BZOJ 4031] [HEOI 2015] 小Z的房间

【BZOJ3624】免费道路

这题大意是有n个点, 给你m条边,其中有一些是水泥路,另一些是鹅卵石路。让你取n-1条边,其中要有k条鹅卵石路,使它成为一棵生成树。

因为有两种路,所以肯定要有几条边是一定要取得,那就先将所有水泥路连边,接着再做生成树,则需要加的边肯定是在答案中的。

这时再判断必定要取的鹅卵石路是否大于k,若大于k则无答案。接着只要将剩下的点做生成树即可