开学第三周。。。。。。。。。真快尼
没有计划的生活真的会误入歧途anytime
表示不开心不开心不开心 每天都觉得自己的生活很忙 又觉得想做的事又没有完成 这学期本来计划重点好好学算法，打码码，臭臭美，做点兼职尼 坚持早起啊，一定一定！！！！坚持到成功为止！要不然之前努力就白费了 我想抽空看电影。。。学做PPt。。。口语。。。不能停。。。。。6级。。。。。觉得时间不过用尼 发现白天的生活就是死人一般啊。。。这些恼人的课ssssss和死板的teachersssssssss 抓 狂 我自我感爆棚了！！！！无心相处 ，，，，， 根本做不上自己的事啊 ~~~~ 社会水太深 宝宝心好累 按时睡觉按时起 练口语 小爷啥时候做我的6题尼 课上的时间还是得好好地吧 白天的空课 留给他们6科 晚上代码算法 java咋办尼 放在这个时间里吧 简单的熟悉还没有做到尼 熟练了就行 关于兼职 小爷心里苦啊 真的有些糟心尼 歇几天 既然是大人了 早晚都要学着平衡这些东西才是尼本月减肥20天！！！！ 最重要的是代码算法 第二阶段啊！！！！不能舍本逐末 !!!!生活不是是眼前的苟且 还有诗和远方 调整好自己 充实精致的自己
hdu1102 Constructing Roads（kruskal）
Constructing Roads
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6701 Accepted Submission(s): 2475
1 to N, and you should build some roads such that every two villages
can connect to each other. We say two village A and B are connected, if
and only if there is a road between A and B, or there exists a village C
such that there is a road between A and C, and C and B are connected.
We
know that there are already some roads between some villages and your
job is the build some roads such that all the villages are connect and
the length of all the roads built is minimum.
<= 100), which is the number of villages. Then come N lines, the i-th
of which contains N integers, and the j-th of these N integers is the
distance (the distance should be an integer within [1, 1000]) between
village i and village j.
Then there is an integer Q (0 <= Q
<= N * (N + 1) / 2). Then come Q lines, each line contains two
integers a and b (1 <= a < b <= N), which means the road
between village a and village b has been built.
which is the length of all the roads to be built such that all the
villages are connected, and this value is minimum.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[];
int n,m;
int cc;
struct edge
{
int u,v,w;
void set(int x,int y,int s)
{
u=x;
v=y;
w=s;
} }e[];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
void kruskal()
{
int ans=;cc=n;
sort(e,e+n*n,cmp);
for(int i=; i<n*n; i++)
{
int x=find(e[i].u);
int y=find(e[i].v);
if(x!=y)
{
fa[x]=y;
ans+=e[i].w;
cc--;
}
}
if(cc==)
printf("%d\n",ans);
} void init()
{
for(int i=; i<n; i++)
fa[i]=i; }
int main()
{
while(cin>>n)
{
init();
int cnt=;int d[][];
for(int i=; i<n; i++)
for(int j=; j<n; j++)
scanf("%d",&d[i][j]);
int Q;
cin>>Q;
int a,b;
for(int i=; i<Q; i++)
{
scanf("%d%d",&a,&b);
d[a-][b-]=;
}
for(int i=; i<n; i++)
for(int j=; j<n; j++)
{ e[cnt].set(i,j,d[i][j]); cnt++;
}
kruskal(); }
return ;
}
快赶上生哪吒了的进度。。。。