反思

首先我要对最近写的题进行一下，反思，首先最近做P1698和P1225这两道题的时候，Debug的时间太长了，消耗我不少时间。所以我觉得是我的做题方式出了问题，我应该在拿到一道题之后，去认真的想，然后思考，大致规划出怎么写，代码实现思路需要详细一些，然后去仔细理解，明白每一个步骤是干什么后，想一想会不会出什么bug，或者特别情况，所有的东西都想清楚了之后，再去认真的把它敲出来，一边敲一边打表Debug，确保自己写的每一步都是对的才行。

并查集

并查集我也是刚刚学会的，所以总结一下。

并查集就是利用father数组来记录下来和每一个点联系的点，然后经过压缩路径之后，所有有关系的点都会指向同一个点，那么这就是一个集合，并查集来寻找两个点是否在同一个集合里面是非常快的。

并查集代码

递归版本：

1
2
3
4
5
6
7
8
int Getfather(int x)
{
    if(father[x]==x) return x;
    int p=Getfather(father[x]);
    Num_Start[x]+=Num_Start[father[x]];
    father[x]=p;
    return father[x];
}

非递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
int Getfather(int k)
{
    int Find=k;
    while(parent[Find]!=Find)
    Find=parent[Find];
    while(Find!=k)
    {
        int x=parent[k];
        parent[k]=Find;
        k=x;
    }
    return Find;
}

银河英雄传

问题描述：

公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。

该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

输入：

第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。以下有T行，每行有一条指令。指令有两种格式：

  1. M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
  2. C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

输出：

如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

题解：

这道题核心就是并查集查询和两个数组depth和conut的处理比较麻烦。我们在计算两个战舰之间的战舰数量的时候需要不断的更新depth和conut，具体方法可以上网上搜索，这道题我之所以卡住的根本原因就是我没有理解算法就开始去敲了，其中搜索Getfather中的时候，更新depth需要根据根节点开始逐步进行跟新，这样确保每次更新的都为正确值，然后这样的话Getfather就需要用递归来写，每次回到上一个父亲节点，但是如果使用非递归版本之后，就没有办法根据根节点更新……尽管有可能爆栈……

所以换是各种算法都要学，然后根据题目的意义进行搞，希望能从今天长达4个小时的纯Debug时间得到教训！

代码：

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a,b,This,father[30001],Num_end[30001],Num_Start[30001];
char s1;
int Getfather(int x)
{
    if(father[x]==x) return x;
    int p=Getfather(father[x]);
    Num_Start[x]+=Num_Start[father[x]];
    father[x]=p;
    return father[x];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=30001;i++)
    {
        father[i]=i;
        Num_end[i]=1;
        Num_Start[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>s1>>a>>b;
        if(s1=='M')
        {
            int x=Getfather(a);
            int y=Getfather(b);
            father[y]=x;
            Num_Start[y]=Num_end[x];
            Num_end[x]=Num_end[x]+Num_end[y];
        }
        if(s1=='C')
        {
            int x=Getfather(a);
            int y=Getfather(b);
            if(x!=y) cout<<-1<<endl;
            else cout<<abs(Num_Start[a]-Num_Start[b])-1<<endl;
        }
    }
    return 0;
}

[noip2010]关押罪犯

刚刚做了这道题，感受到了并查集的超级神奇之处，所以特意总结下来

题目描述：

S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并 造成影响力为 c 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表， 然后上报到 S 城 Z 市长那里。公务繁忙的 Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那 么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入：

输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N 和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M 行每行为三个正整数 aj，bj，cj，表示 aj 号和 bj 号罪犯之间存在仇恨，其怨气值为 cj。数据保证1 ≤ a j < b j ≤ N ，0 < c j ≤ 1,000,000,000 ，且每对罪犯组合只出现一 次。

输出:

输出文件 prison.out 共 1 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱 中未发生任何冲突事件，请输出 0。

题解

这道题最开始是利用二分图匹配来写的，但是在网上看到了神奇的并查集的写法，真的是效率非常非常高！并且是超级好写，无论是相对于二分答案还是二分图匹配，代码量是非常小的。

那么我们可以建立两个集合，一个集合表示这这两个不在一个监狱里，另一个集合表示这两个人在一个监狱里面，那么我们就可以将所有的怒气值从大到小进行一个排序，然后进行枚举，查找他们所在的集合，然后判断是不是出现了冲突（在同一个集合里面），如果出现了冲突，那么这个值就是怒气值的最大值，直接输出就好，如果没有出现冲突，那么将这两个放在一个并查集（表示不在同一个监狱的并查集）里面，表示这两个人是在不同的监狱里面。然后继续循环。

其实这道题就是运用到了并查集的容斥原理，和一点小小的贪心，我们将尽量怒气值比较大的放在不同的监狱里面，然后放次大的，如果出现冲突，也就是说在前面的安排之下，没有办法将当前的两个人分开，那么这两个人只能在一个监狱里面，这也就是最小的怒气值。

算法真的是超级神奇啊！！！

代码：

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct Edge
{
    int x;
    int y;
    int v;
}a[120000];
int n,m,f[120000];
bool mycmp( Edge a,Edge b)
{ return a.v>b.v; }
inline int In()
{
    int This=0,F=1; char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
int Find(int x)
{
    if(f[x]==x) return x;
    f[x]=Find(f[x]);
    return f[x];
}
int main()
{
    n=In(); m=In();
    for(int i=1;i<=m;i++)
    {
        a[i].x=In();
        a[i].y=In();
        a[i].v=In();
    }
    for(int i=1;i<=n*2;i++) f[i]=i;
    sort(a+1,a+m+1,mycmp);
    for(int i=1;i<=m;i++)
    {
        int xx=Find(a[i].x);
        int yy=Find(a[i].y);
        if(xx==yy)
        {
            cout<<a[i].v<<endl;
            return 0;
        }
        f[yy]=Find(a[i].x+n);
        f[xx]=Find(a[i].y+n);
    }
    cout<<false<<endl;
    return 0;
}