글 읽기 - 반례를 못 찾겠습니다

fkam12 3년 전 0

크루스칼로 풀려고하는데 예제는 나옵니다만

왜 틀린지 반례를 못 찾겠습니다.

도와주시면 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;

int unf[201];
int mat[201][201];
typedef struct Road{
	int from;
	int to;
	int cost;
	Road(int f, int t, int c) {
		from = f;
		to = t;
		cost = c;	
	}
	bool operator<(const Road &r) const{
		return cost < r.cost;	
	}
}Road;

int Find(int v){
	if(unf[v] == v) return v;
	else return unf[v] = Find(unf[v]);	
}

void Union(int a, int b){
	a = Find(a);
	b = Find(b);
	if(a!=b) {
		unf[a] = b;
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("input.txt", "rt", stdin);
	int n, i, j, res = 0, cnt = 0, tmp;
	// 도로 
	vector<Road> Ro;
	// 추가 도로 
	vector<pair<int, int> > addRo;
	cin >> n;
	if(n == 1) {
		cin >> tmp;
	}
	for(i = 1; i <= n; i++) unf[i] = i;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			cin >> mat[i][j];		
		}
	}
	
	for(i = 1; i <= n; i++){
		for(j = i+1; j <= n; j++){
			if(mat[i][j] > 0 && mat[i][j] != 1000) {
				Ro.push_back(Road(i, j, mat[i][j]));
			}
			else if(mat[i][j] < 0) {
				Ro.push_back(Road(i, j, abs(mat[i][j])));
                // 음수이면 기존 연결되어 있으므로 바로 유니온 후 절대값을 더함
				Union(i, j);
				res = res + abs(mat[i][j]);
			}
		}
	}

	sort(Ro.begin(), Ro.end());
	for(i = 0; i < Ro.size(); i++){
		int c1 = Find(Ro[i].from);
		int c2 = Find(Ro[i].to);
		if(c1 != c2) {
			Union(c1, c2);
			addRo.push_back(make_pair(Ro[i].from, Ro[i].to));
			res = res + Ro[i].cost;
			cnt++;
		}
	}
	if(n == 1) cout << abs(tmp) << " " << cnt << '\n';
	else {
		cout << res << " " << cnt << '\n';
	}
	for(auto s : addRo) cout << s.first << " " << s.second << '\n';
	
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못 찾겠습니다

fkam12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말