pat1001. Battle Over Cities - Hard Version 解题报告

50 阅读 0 评论 33 点赞

我是靠谱客的博主典雅大雁，最近开发中收集的这篇文章主要介绍pat1001. Battle Over Cities - Hard Version 解题报告，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/**
题目：删去一个点，然后求出需要增加最小代价的边集合生成连通图
思路：
prim+最小堆
1.之前图中未破坏的边必用，从而把两两之间可互达的点集合合并成一个点
2.求出不同点集合的最短距离，用prim+最小堆求出最小生成树

kruskal
1.之前图中未破坏的边必用，全部加到图中
2.途中被破坏的边按照边权从小到大的顺序依次加入图中，直到图变为连通图

两个方法的对应一个点的最小生成树的复杂度都是nlogm，第二个方法较好写

优化：
1.未破坏的边直接加入图中
2.当有n-2条边(当前删去一个点后，图中n-1个点)在图中时，直接结束建生成树

另外：
求图的连通性：
有向强连通
无向并查集

当然，并查集好写很多。。。
**/


1 #include <stdio.h>

2 #include <stdlib.h>

3 #define maxn 500

4 #define maxm 125000

5 #define maxdist 100000

6

7 /**

8 题目：删去一个点，然后求出需要增加最小代价的边集合生成连通图

9 思路：
 10 prim+最小堆
 11 1.之前图中未破坏的边必用，从而把两两之间可互达的点集合 合并成一个点
 12 2.求出不同点集合的最短距离，用prim+最小堆求出最小生成树
 13
 14 kruskal
 15 1.之前图中未破坏的边必用，全部加到图中
 16 2.途中被破坏的边按照边权从小到大的顺序依次加入图中，直到图变为连通图
 17
 18 两个方法的对应一个点的最小生成树的复杂度都是nlogm，第二个方法较好写
 19
 20 优化：
 21 1.未破坏的边直接加入图中
 22 2.当有n-2条边(当前删去一个点后，图中n-1个点)在图中时，直接结束建生成树
 23
 24 另外：
 25 求图的连通性：
 26 有向 强连通
 27 无向 并查集
 28
 29 当然，并查集好写很多。。。
 30 **/
 31
 32 struct node
 33 {
 34
long x,y,c,s;
 35 }edge0[maxm+1],edge1[maxm+1];
 36 long fa[maxn+1];
 37
 38 long max(long a,long b)
 39 {
 40
if (a>b)
 41
return a;
 42
else
 43
return b;
 44 }
 45
 46 int cmp(const void *a,const void *b)
 47 {
 48
//先把未损坏的路径加入图中
 49
if ((*(struct node *)a).s < (*(struct node *)b).s)
 50
return 1;
 51
else if ((*(struct node *)a).s > (*(struct node *)b).s)
 52
return -1;
 53
//再对已损坏的路径进行排序，用kruskal算法,m log m
 54
else if ((*(struct node *)a).c < (*(struct node *)b).c)
 55
return 1;
 56
else
 57
return -1;
 58 }
 59
 60 long getfather(long d)
 61 {
 62
if (fa[d]==d)
 63
return d;
 64
else
 65
return getfather(fa[d]);
 66 }
 67
 68 int main()
 69 {
 70
long i,j,n,m,p,q,x,y,c,s,g,fx,fy,ans,cost[maxn+1];
 71
while (scanf("%ld%ld",&n,&m)!=EOF)
 72 
{
 73
p=0;
 74
q=0;
 75
for (i=0;i<m;i++)
 76 
{
 77
scanf("%ld%ld%ld%ld",&x,&y,&c,&s);
 78
if (s==1)
 79 
{
 80
p++;
 81
edge1[p].x=x; edge1[p].y=y; edge1[p].c=c; edge1[p].s=s;
 82 
}
 83
else
 84 
{
 85
q++;
 86
edge0[q].x=x; edge0[q].y=y; edge0[q].c=c; edge0[q].s=s;
 87 
}
 88 
}
 89
qsort(edge0+1,q,sizeof(struct node),cmp);
 90
 91
ans=0;
 92
for (i=1;i<=n;i++)
 93 
{
 94
for (j=1;j<=n;j++)
 95
fa[j]=j;
 96
g=0;
 97
//edge - exist
 98
for (j=1;j<=p;j++)
 99 
{
100
if (edge1[j].x==i || edge1[j].y==i) continue;
101
fx=getfather(edge1[j].x);
102
fy=getfather(edge1[j].y);
103
if (fx==fy) continue;
104
fa[fx]=fy;
105
g++;
106
if (g==n-2)
107
break;
108 
}
109
//优化
110
if (g==n-2)
111 
{
112
cost[i]=0;
113
continue;
114 
}
115
116
//edge - not exist
117
cost[i]=0;
118
for (j=1;j<=q;j++)
119 
{
120
if (edge0[j].x==i || edge0[j].y==i) continue;
121
fx=getfather(edge0[j].x);
122
fy=getfather(edge0[j].y);
123
if (fx==fy) continue;
124
fa[fx]=fy;
125
g++;
126
cost[i]+=edge0[j].c;
127
//优化
128
if (g==n-2)
129
break;
130 
}
131
if (g<n-2)
132
cost[i]=maxdist;
133
ans=max(ans,cost[i]);
134 
}
135
if (ans>0)
136 
{
137
for (i=1;i<=n;i++)
138
if (cost[i]==ans)
139 
{
140
printf("%ld",i);
141
break;
142 
}
143
for (j=i+1;j<=n;j++)
144
if (cost[j]==ans)
145
printf(" %ld",j);
146
printf("n");
147 
}
148
else
149
printf("0n");
150 
}
151
return 0;
152 }