生成树算法
#include "stdio.h"
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int table[105][105];
int e[5005][3];
int qu[5005];
int node[105];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int judge(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if(e[qu[a]][2]>e[qu[b]][2])return 1;
if(e[qu[a]][2]<e[qu[b]][2])return -1;
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void swap(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t;
t=qu[a];
qu[a]=qu[b];
qu[b]=t;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int partion(int low,int high,int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
while(low<=high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(low<p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(judge(low,p)>0) {swap(low,p);p=low;}
low++;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(high>p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(judge(high,p)<0) {swap(high,p);p=high;}
}
high--;
}
}
return p;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void qsort(int left,int right)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int middle;
if(left<right)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
middle=(left+right)/2;
middle=partion(left,right,middle);
qsort(left,middle-1);
qsort(middle+1,right);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void make(int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i;
for(i=0;i<p;i++)node[i]=-1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find(int a)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i;
if(node[a]<0)return a;
i=find(node[a]);
node[a]=i;
return i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void un(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int ra=find(a);
int rb=find(b);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(node[ra]<node[rb]) {node[ra]+=node[rb];node[rb]=ra;}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) else {node[rb]+=node[ra];node[ra]=rb;}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int n,q,l,r;
int i,j,en;
int sum;
while(scanf("%d",&n)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=0;j<n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d",&table[i][j]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf("%d",&q);
for(i=0;i<q;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d%d",&l,&r);
table[l-1][r-1]=table[r-1][l-1]=0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
en=0;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=0;j<n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(j<i) {e[en][0]=i;e[en][1]=j;e[en++][2]=table[i][j];}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0;i<en;i++)qu[i]=i;
qsort(0,en-1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sum=0;
make(n);
for(i=0;i<en;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(find(e[qu[i]][0])!=find(e[qu[i]][1]))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
sum+=e[qu[i]][2];
un(e[qu[i]][0],e[qu[i]][1]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n",sum);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|