首页 > 代码库 > pat1001. Battle Over Cities - Hard Version 解题报告
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("0\n"); 150 } 151 return 0; 152 }
pat1001. Battle Over Cities - Hard Version 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。