P2330 [SCOI 2005] 바 쁜 도시

제목 설명
도시 C 는 매우 바 쁜 대도시 로 도시 안의 도로 가 매우 붐벼 서 시장 은 그 중의 도 로 를 개조 하기 로 결정 했다.도시 C 의 도 로 는 이렇게 분포 되 어 있다. 도시 에는 n 개의 교차로 가 있 고 어떤 교차로 사이 에는 도로 가 연결 되 어 있 으 며 두 개의 교차로 사이 에는 최대 한 개의 도로 가 연결 되 어 있다.이 도 로 는 양 방향 이 고 모든 교차 로 를 직간 접적 으로 연결 했다.모든 도로 에 하나의 가치 가 있 는데 가치 가 작 을 수록 이 도로 가 바 쁠 수록 개조 가 필요 하 다 는 것 을 나타 낸다.그러나 시 정부의 자금 이 제한 되 어 시장 이 개 조 를 원 하 는 길 은 적 을 수록 좋다. 그래서 그 는 다음 과 같은 요 구 를 했다.
1. 개 조 된 그 도 로 는 모든 교차 로 를 직간 접적 으로 연결 할 수 있다.2. 요구 1 을 만족 시 키 는 상황 에서 개 조 된 도 로 는 되도록 적다.3. 요구 1, 2 를 만족 시 키 는 상황 에서 개 조 된 도로 중 가치 가 가장 큰 도로 의 가 치 는 최대한 작다.
임무: 시 기획 국 의 당신 으로서 최선 의 결정 을 내 려 야 합 니 다. 그 도 로 를 선택 하면 건설 되 어야 합 니 다.
입력 형식
첫 번 째 줄 에는 두 개의 정수 n 이 있 는데 m 는 도시 에 n 개의 교차로, m 개의 도로 가 있다 는 것 을 나타 낸다.
다음 m 행 은 모든 도로 에 대한 설명 이다. u, v, c 는 교차로 u 와 v 사이 에 도로 가 연결 되 어 있 고 값 은 c 이다.(1≤n≤300，1≤c≤10000，1≤m≤100000)
출력 형식
두 개의 정수 s, max 는 당신 이 몇 개의 도 로 를 선 택 했 는 지, 점수 가 가장 큰 도로 의 점수 가 얼마 인지 나타 낸다.
입 출력 샘플
입력 \ # 1

출력 \ # 1

3 6

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 305; 

struct Node{
	int u,v,w;
	Node(int u,int v,int w){
		this->u = u;
		this->v = v;
		this->w = w;
	}
};
vector edge;
int father[MAXN]; //father[i]=u   i      u，  ：       ，            。 

int findFather(int x){
	int z = x;  //  x   
	int temp;
	while(x != father[x]){  // while    x   ，      x           
		x = father[x];
	}
	/*
	**   z  （   z     x），      ， 
	**                    x。 
	**        "    "，       ，    。 
	**/
	while(z != father[z]){ //    while(x != father[x])     
		temp = z;   //  z   
		z = father[z];  //    x = father[x];     
		father[temp] = x; //               x
	}
	return x; //  x            ，          
}

//  x y         ，    ， y        x    
bool unionFather(int x,int y){
	int flag = false;
	int fx = findFather(x);
	int fy = findFather(y);
	if(fx != fy){  //  x y           ， x---y            。 
		father[fy] = fx;
		flag = true; 
	} 
	return flag;
} 

void initFather(int n){
	for(int i=0;i<=n;i++){
		father[i] = i;
	}
}

bool cmp(Node &node1,Node &node2){
	return node1.w < node2.w;
}

int edgeNum; //          
int maxCost; //             
bool kruskal(int n){
	int u,v,c,fu,fv;
	edgeNum = 0; //          
	maxCost = -1;//    
	initFather(n); 
	sort(edge.begin(),edge.end(),cmp); //    c         
	for(int i=0;i>n>>m;
	while(m--){
		cin>>u>>v>>c;
		edge.push_back(Node(u,v,c));
	} 
	kruskal(n);
	cout<

P2330 [SCOI 2005] 바 쁜 도시

좋은 웹페이지 즐겨찾기