烤炉ver💯 寄雨丶
#崔珉豪#
关注数: 0 粉丝数: 1 发帖数: 95 关注贴吧数: 30
automarker(一个oj)说我timelimitexceeded 作业让我们输入顶点数和无向图邻接矩阵得到MST的路径长,我用的kruskal。 简单的case我已经通过编译了,但是hard case我就过不了(比如1000个顶点的矩阵) 但我觉得我的已经很减时间复杂度了,大佬救急求助哇 #include<stdio.h> #include<stdlib.h> #define Max 1001 typedef struct{ int vex1; int vex2; int weight; }Edge; typedef struct{ int vex[Max]; Edge edge[Max]; int vexnum; int edgenum; }EdgeGraph; int adjmatrix[1000][1000]; int parent[1000]; int rank[1000]; EdgeGraph G; void init(int n) { for (int i = 0; i < n; ++i){ parent[i] = i; rank[i] = 1; } } int find(int i) { if (parent[i] == i) return i; else{ parent[i] = find(parent[i]); return parent[i]; } } void Union(int x, int y)//通过秩的比较,进行路径压缩 { if (x == y) return; if (rank[x] < rank[y]) parent[x] = y; if (rank[x] > rank[y]) parent[y] = x; if (rank[x] == rank[y]){ rank[y]++; parent[x] = y; } } int main() { int i=0; int result[500]; for(int j=0; j<Max; j++){ G.vex[j]=j; } int vertex=0; scanf("%d",&vertex); while(vertex!=0){ G.vexnum = vertex; int num=0; for( int m=0; m<vertex; m++){ for( int n=0; n<vertex; n++){ scanf("%d",&adjmatrix[m][n]); if( m<n && adjmatrix[m][n]!=0 ){ G.edge[num].vex1=m; G.edge[num].vex2=n; G.edge[num].weight=adjmatrix[m][n]; num++; } } } G.edgenum = num; Edge temp; for( int n=0; n<num-1; n++){ for( int m=n+1; m<num; m++){ if( G.edge[n].weight > G.edge[m].weight ){ temp = G.edge[n]; G.edge[n] = G.edge[m]; G.edge[m] = temp; } } } int m; int root1,root2; int length=0; for(int a=0; a<vertex; a++){ init(vertex); } for( m=0; m<G.edgenum; m++){ root1=find(G.edge[m].vex1); root2=find(G.edge[m].vex2); if( root1!=root2 ){ length += G.edge[m].weight; Union(root1,root2); } } result[i]=length; i++; scanf("%d",&vertex); } for(int a=0; a<i; a++){ printf("%d\n",result[a]); } return 0; }
1 下一页