| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:0ms,10点全过,cin和coutIn Reply To:Re:0ms,10点全过,cin和cout Posted by:suchuanzhi at 2019-11-12 16:59:57 说好的行末可能有若干个空格呢?这什么都不处理就能过的吗。
谁能帮我指点一下。测试数据全过WA代码附上。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1000;
int k,n,r[maxn];
struct Node{
int u,v,w;
bool const operator <(const Node &a) const{
return w<a.w;
}
}e[maxn];
int find(int x) {
if(x!=r[x]) x=find(r[x]);
else return x;
}
void kruskal() {
int cnt=0,ans=0;
for(int i=0;cnt<n-1 && i<k; i++) {
int t1=find(e[i].u);
int t2=find(e[i].v);
if(t1!=t2) {
r[t1]=t2;
ans+=e[i].w;
cnt++;
}
}
cout<<ans<<endl;
}
int main(){
int m;
while(cin>>n && n) {
k=0;
for(int i=0; i<n-1; i++) {
char c1;
cin>>c1>>m;
for(int j=0; j<m; j++) {
char c2;
int d;
cin>>c2>>d;
e[k].u=(c1-'A');
e[k].v=(c2-'A');
e[k].w=d;
k++;
}
}
sort(e,e+k);
for(int i=0; i<n; i++)
r[i]=i;
kruskal();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator