Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:0ms,10点全过,cin和cout

Posted by suchuanzhi at 2019-11-12 17:02:30 on Problem 1251
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator