# Untitled

unknown
c_cpp
2 months ago
4.6 kB
8
Indexable
Never
```// AC(6/6) 2700ms
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

// To represent Disjoint Sets
struct DisjointSets{
int *parent, *rnk;
int n;

// Constructor.
DisjointSets(int n){
// Allocate memory
this->n = n;
parent = new int[n+1];
rnk = new int[n+1];

// Initially, all vertices are in
// different sets and have rank 0.
for (int i = 0; i <= n; i++){
rnk[i] = 0;

//every element is parent of itself
parent[i] = i;
}
}

// Find the parent of a node 'u'
// Path Compression
int find(int u){
/* Make the parent of the nodes in the path
from u--> parent[u] point to parent[u] */
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}

// Union by rank
void merge(int x, int y){
x = find(x), y = find(y);

/* Make tree with smaller height
a subtree of the other tree */
if (rnk[x] > rnk[y])
parent[y] = x;
else // If rnk[x] <= rnk[y]
parent[x] = y;

if (rnk[x] == rnk[y])
rnk[y]++;
}
};

class edge{  //自製的容器，用來表達edge
public:
edge():s(0),e(0),cost(0){}
edge(int s,int e,int cost):s(s),e(e),cost(cost){}
int s;
int e;
int cost;
bool operator<(const edge &B) const{  //for the purpose of reverse sorting
return cost < B.cost;
}
bool operator==(const edge &B) const{
return (B.s == s) && (B.e == e) && (B.cost == cost);
}
};

int N;
int E;
long long Cost = LLONG_MAX;
vector<edge> graph;

long long MST_select(edge A,DisjointSets &ds){  //開場先挑A edge
long long cost = 0;

int u = A.s,v = A.e;

int set_u = ds.find(u);
int set_v = ds.find(v);
ds.merge(set_u, set_v);
cost += A.cost;

for(auto &a:graph){

if(E == N-1) break;
if(a==A) continue;
if(cost > Cost) break;

int u = a.s,v = a.e;

int set_u = ds.find(u);
int set_v = ds.find(v);

if (set_u != set_v) {
// Merge two sets
ds.merge(set_u, set_v);
cost += a.cost;
}
}

// re-initialize，為了下一把還能重複使用Disjoint set，幫它重新初始化一下
for (int i = 0; i <= N; i++) {
ds.rnk[i] = 0;
//every element is parent of itself
ds.parent[i] = i;
}

return cost;
}

long long MST_skip(edge A,DisjointSets &ds){   //必略過A edge不挑
long long cost = 0;

for(auto &a:graph){

if(E == N-1) break;
if(a==A) continue;
if(cost > Cost) break;

int u = a.s,v = a.e;

int set_u = ds.find(u);
int set_v = ds.find(v);

if (set_u != set_v) {
// Merge two sets
ds.merge(set_u, set_v);

cost+=a.cost;
}
}

// re-initialize，為了下一把還能重複使用Disjoint set，幫它重新初始化一下
for (int i = 0; i <= N; i++) {
ds.rnk[i] = 0;
//every element is parent of itself
ds.parent[i] = i;
}

return cost;
}

int main(){
std::ios::sync_with_stdio(false);

cin >> N;
cin >> E;
for(int i=0;i<E;i++){  //輸入所有的邊
int s,e,c;
cin >> s >> e >> c;
graph.push_back(edge(s,e,c));
}

sort(graph.begin(),graph.end());  //把所有的邊依照cost作升序排列

DisjointSets ds(N);  //建立一個Disjoint set，為了在Kruscal中O(logN) detect cycle (要很客家的重複使用，不然要吃MLE)

Cost = MST_skip(edge(),ds);    //找到一般的，MST的cost
int essential_cnt = 0,secondary_cnt = 0;

/*對每條邊進行考慮
拿掉這條邊就造不出MST(cost > min_cost，Kruscal失敗) -> 這條邊存在於所有MST (essential link)
造得出包含這條邊的MST(cost == min_cost，Kruscal成功) -> 這條邊存在於某些(有可能全部)MST中 (至少也是secondary link)*/
for(auto &a:graph){
if(MST_skip(a,ds) > Cost) essential_cnt++;
else if(MST_select(a,ds) == Cost) secondary_cnt++;
}

cout << Cost <<'\n' << essential_cnt <<'\n' << secondary_cnt <<'\n';
return 0;
}```