CCF CSP 2018 - 12 - 4 데이터 센터

code：
누 드 의 최소 생 성 나무 입 니 다.

#include
#include
#include
#include
#include
#include
#include
#define rep(i,j,k) for(int i = j; i < k; ++i)
#define mst(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define se second
#define fi first
using namespace std;
typedef long long LL;
const int MAXN = 500000+5;
bool mark[MAXN];
int cnt;
struct Edge{
	int f,to,w;
	Edge(){}
	Edge(int ff,int tt,int ww):f(ff),to(tt),w(ww){}
	bool operator  obj.w;
	}
};

vector G[MAXN];
priority_queue pq;
int n,m,a,b,c;
int tol; //     
 
void visit(int cur){
	mark[cur] = true;
	++cnt;
	for(int i = 0; i < G[cur].size(); ++i){
		Edge &e = G[cur][i];
		if(!mark[e.to]){
			pq.push(e);
		}
	}
}

void prim(int s){
	int ans = -1;
	cnt = 1;
	mst(mark,false);
	mark[s] = true;
	for(int i = 0; i < G[s].size(); ++i){
		pq.push((Edge)G[s][i]);
	}
	int to;
	while(cnt < n && !pq.empty()){
		Edge e = pq.top();
		pq.pop();
		to = e.to;
		if(mark[to]) continue;
		ans = max(ans,e.w);
		visit(to);
	}
	cout << ans << endl;
}

int main()
	{
		
		//freopen("input.txt","r",stdin);
		ios::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);
		int root;
		cin >> n >> m >> root;
		rep(i,0,m){
			cin >> a >> b >> c;
			G[a].push_back(Edge(a,b,c));
			G[b].push_back(Edge(b,a,c));
		} 
		prim(root);

		return 0;
	}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CCF CSP 201509 - 4 고속도로 [Kosaraju]

제목: N 개의 점, M 개의 변 에 방향 그림 이 있 고 몇 쌍 (x, y) (x, y) (x, y) 이 x x x 에서 y y 까지 만족 할 수 있 으 며 y y 에서 x x x x x x x x x 까지 도 가...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

CCF CSP 2018 - 12 - 4 데이터 센터

좋은 웹페이지 즐겨찾기