首页 > 代码库 > poj2421
poj2421
1 //Accepted 312 KB 63 ms 2 //kruskal算法,求最小生成树,把已经存在边的两点之间的权值置为0; 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 const int MAXN = 105; 8 const int inf = 100000000; 9 const int MAXM =MAXN*MAXN; 10 struct node 11 { 12 int u,v,c; 13 node(int u,int v,int c):u(u),v(v),c(c) 14 { 15 16 } 17 node() 18 { 19 20 } 21 }p[MAXM]; 22 int cmp(node x,node y) 23 { 24 return x.c<y.c; 25 } 26 bool flag[MAXN][MAXN]; 27 int a[MAXN][MAXN]; 28 int n; 29 int Q; 30 int e; 31 int f[MAXN]; 32 int ans; 33 void addnode(int u,int v,int c) 34 { 35 p[e++]=node(u,v,c); 36 } 37 void build() 38 { 39 for (int i=0;i<=n;i++) 40 { 41 f[i]=i; 42 } 43 } 44 int find(int x) 45 { 46 if (f[x]==x) return x; 47 return f[x]=find(f[x]); 48 } 49 void union_set(int x,int y) 50 { 51 int fx=find(x),fy=find(y); 52 if (fx!=fy) 53 { 54 f[fy]=fx; 55 } 56 } 57 void kruskal() 58 { 59 int cnt=0; 60 ans=0; 61 sort(p,p+e,cmp); 62 for (int i=0;i<e;i++) 63 { 64 int x=p[i].u; 65 int y=p[i].v; 66 if (find(x)!=find(y)) 67 { 68 union_set(x,y); 69 ans+=p[i].c; 70 cnt++; 71 } 72 if (cnt==n-1) return ; 73 } 74 } 75 int main() 76 { 77 while (scanf("%d",&n)!=EOF) 78 { 79 build(); 80 for (int i=0;i<n;i++) 81 for (int j=0;j<n;j++) 82 scanf("%d",&a[i][j]); 83 scanf("%d",&Q); 84 e=0; 85 memset(flag,0,sizeof(flag)); 86 for (int i=0;i<Q;i++) 87 { 88 int x,y; 89 scanf("%d%d",&x,&y); 90 flag[x-1][y-1]=1; 91 flag[y-1][x-1]=1; 92 } 93 for (int i=0;i<n;i++) 94 { 95 for (int j=0;j<n;j++) 96 { 97 if (i!=j) 98 { 99 if (flag[i][j]==1) 100 { 101 addnode(i,j,0); 102 } 103 else 104 { 105 addnode(i,j,a[i][j]); 106 } 107 } 108 } 109 } 110 kruskal(); 111 printf("%d\n",ans); 112 } 113 return 0; 114 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。