acmicpc.net 1922(스패닝 트리), 1197(스패닝 트리), 2887(스패닝 트리)

https://www.acmicpc.net/problem/1922, https://www.acmicpc.net/problem/1197

가장 기본적인 최소 신장 트리 문제. 둘다 문제가 동일하다.

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int n,m,a,b,c;
vector<pair<int,int>> adj[100001];

struct DisjointSet {
	vector<int> parent, rank;

	DisjointSet(int n) : parent(n), rank(n, 1) {
		for(int i = 0; i < n; i++)
			parent[i] = i;
	}

	int find(int u) {
		if(u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}

	void merge(int u, int v) {
		u = find(u); v = find(v);
		if(u == v) return;
		if(rank[u] > rank[v]) swap(u, v);
		if(rank[u] == rank[v]) rank[v]++;
		parent[u] = v;
	}
};

int kruskal()
{
	int ret = 0;
	//vector<pair<int,int> > selected;
	vector<pair<int,pair<int,int> > > edges;
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < adj[i].size(); j++)
			{
				edges.push_back(make_pair(adj[i][j].second, make_pair(i,adj[i][j].first)));
			}
	sort(edges.begin(), edges.end());
	DisjointSet d(n);
	for(int i = 0; i < edges.size(); i++)  {
		int cost = edges[i].first;
		int u = edges[i].second.first;
		int v = edges[i].second.second;
		if(d.find(u) == d.find(v))
			continue;
		d.merge(u,v);
		//selected.push_back(make_pair(u,v));
		ret += cost;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); 
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		adj[a-1].push_back(make_pair(b-1,c));
	}
	cout<<kruskal()<<endl;
}

https://www.acmicpc.net/problem/2887

어렵다. 코드를 짜기전에 생각을 해봐야 한다.

모든 행성끼리 연결하자면 행성이 최대 10만개가 있을수 있으므로 10만*10만개의 반복문이 된다.

이러면 시간초과난다. 어떻게해야될까.?

다른 방법은 모르겠는데 한참을 생각하다가 x,y,z에 대한 vector를 만들고, (x값, 행성번호) 형식으로 저장해두었다. 그 이후 x를 x값에 대해서 정렬, y,z도 각각의 y,z에 대해서 정렬 후 반복문을 돌면서 

x에 대해서 : 0번째 행성과 1번째 행성을 연결시켜줌, 1번째 행성과 2번째 행성~~ 이런식으로 y,z까지 다 연결해줬다. 이러면 최대 시간복잡도가 3*10만 즉 3n밖에 안나온다. n*n에서 3n으로 줄어서 그런지 시간초과없이 통과했다.

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int n,a,b,c;
vector<pair<int, int>> x,y,z;
//long long planet[100001][3];
long long INF = 999999999999;
vector<pair<long long, long long>> adj[100001];
 
struct DisjointSet {
    vector<int> parent, rank;
 
    DisjointSet(int n) : parent(n), rank(n, 1) {
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }
 
    int find(int u) {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        if(rank[u] == rank[v]) rank[v]++;
        parent[u] = v;
    }
};
 
long long kruskal()
{
    long long ret = 0;
    //vector<pair<int,int> > selected;
    vector<pair<long long,pair<long long,long long> > > edges;
     
    for(int i = 0; i < n; i++)
        for(int j = 0; j < adj[i].size(); j++)
            {
                edges.push_back(make_pair(adj[i][j].second, make_pair(i,adj[i][j].first)));
            }
    sort(edges.begin(), edges.end());
    DisjointSet d(n);
    for(int i = 0; i < edges.size(); i++)  {
        long long cost = edges[i].first;
        int u = edges[i].second.first;
        int v = edges[i].second.second;
        if(d.find(u) == d.find(v))
            continue;
        d.merge(u,v);
        //selected.push_back(make_pair(u,v));
        ret += cost;
    }
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c; 
		x.push_back(make_pair(a,i)); //벡터에 값을 입력받음. 
		y.push_back(make_pair(b,i));
		z.push_back(make_pair(c,i));
    }
	sort(x.begin(), x.end()); //정렬
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());
    //for(int i=0;i<n;i++)
	//	cout<<x[i].first<<" "<<x[i].second<<endl;
	//cout<<endl;
 
    for(int i=0;i<n-1;i++) //요기가 포인트.
    {
		adj[x[i].second].push_back(make_pair(x[i+1].second, abs(x[i].first - x[i+1].first)));
		adj[y[i].second].push_back(make_pair(y[i+1].second, abs(y[i].first - y[i+1].first)));
		adj[z[i].second].push_back(make_pair(z[i+1].second, abs(z[i].first - z[i+1].first)));
    }
    //adj[a-1].push_back(make_pair(b-1,c));//a~b가는데 c비용이 든다.
    cout<<kruskal()<<endl;
}