首页 > 代码库 > [Kruskal][jzyzoj1224]:连接格点

[Kruskal][jzyzoj1224]:连接格点

  犯了个很智障的错误,本来以为是读入出了问题,结果往kruskal函数里一看。。。。1-2=-1,-1*1000+1=-999,所以RE了。。。下面给出题面:

  技术分享

  由题意我们好像看不出来这是个最小生成树。最初我以为这是一道纯贪心就能AC的题,然而仔细画了画图发现并不是这样,如果用贪心的方法算每列上存在的边的条数并不行,因为一列上可以不存在任意一条边,但是如果说通过一个点生成的长边通向这一列上的另外一点的话,这两点之间是不需要再建立一条边的

  这样的话我们可以用图的思想:已经连通的几条边我们可以看做是权值为0的边,还未连通的边我们可以看做是横向权值为1,纵向权值为2的边,然后建图就可以。不过建图的时候需要注意要把二维变为一维

  但是如果将所有的可建立的边记录起来的话不免有些麻烦,我们可以想一个更简便的方法。

  还是贪心的思想:我们先读入已经连好的边,因为这些连好的边的权值为0,所以我们优先用并查集将这两个点合并,即这两点之间不需要再连额外的边,然后在逐个合并的时候不需要再建立边,因为每条边都是横向或是纵向的,而连接纵向的边的权值相对较小,所以我们可以优先连接纵向的边,然后连接横向的边,这样就能解决这个问题了。

  注意记录已经连接的边数,如果边数等于点数-1的话就不需要再连接了,此时一定为最优解。

  代码如下:

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int m,n,father[1000010],ans=0,len=0,sum=0;
 5 int getfather(int x)
 6 {
 7     int y=x;
 8     while (father[y]!=y)    y=father[y];
 9     while (father[x]!=x)
10     {
11         int temp=father[x];
12         father[x]=y;
13         x=temp;
14     }
15     return y;
16 }
17 
18 void init()
19 {
20     scanf("%d%d",&m,&n);
21     for (int i=1;i<=m*n;i++)    father[i]=i;
22     int x1,y1,x2,y2,i=0;
23     while    (scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF)
24     {
25         i++;
26         int f1=getfather((x1-1)*n+y1),f2=getfather((x2-1)*n+y2);
27         if (f1!=f2)
28         {
29             father[f1]=f2;
30             sum++;
31         }
32     }
33 }
34 
35 void kruskal()
36 {
37     for (int i=1;i<=n;i++)
38         for (int j=2;j<=m;j++)//枚举纵向的边,n要放在外层,注意j应当从2开始枚举,防止数组越界
39         {
40             if (sum==m*n-1)    return;        //判断是否已建立足够的边
41             int f1=getfather((j-1)*n+i),f2=getfather((j-2)*n+i);    //注意二维变一维
42             if (f1!=f2)
43             {
44                 father[f1]=f2;
45                 ans++;    sum++;
46             }
47         }
48     for (int i=1;i<=m;i++)
49         for (int j=2;j<=n;j++)//枚举横向的边,n放在内层,j从2开始,防止枚举上一行最后一列到本行第一列的边
50         {
51             if (sum==m*n-1)    return;        //判断是否已建立足够的边
52             int f1=getfather((i-1)*n+j),f2=getfather((i-1)*n+j-1);
53             if (f1!=f2){
54                 father[f1]=f2;
55                 ans+=2; sum++;
56             }
57         }
58 }
59 
60 int main()
61 {
62     init();
63     kruskal();
64     printf("%d\n",ans);
65     return 0;
66 }
AC代码

 

[Kruskal][jzyzoj1224]:连接格点