#include<bits/stdc++.h>
#define N 300
using namespace std;
int node, edge;
struct str
{
int u, v, w;
};
vector<str>v1, v2;
vector<int>v3;
int parent[N];
bool compare(str a, str b)
{
return a.w < b.w;
}
int finds(int x)
{
if(parent[x] < 0)
return x;
return parent[x] = finds(parent[x]);
}
int unions(int a, int b, int w)
{
int u = finds(a);
int v = finds(b);
if(u == v)
return 0;
else
{
if(parent[u] <= parent[v])
{
parent[u] += parent[v];
parent[v] = u;
}
else
{
parent[v] += parent[u];
parent[u] = v;
}
return w;
}
}
int mst()
{
for(int i=1; i<=node; i++)
parent[i] = -1;
int mn = 0, cnt = 0;
for(int i=1; i<v1.size(); i++)
{
int a = v1[i].u;
int b = v1[i].v;
int c = v1[i].w;
int s = unions(a, b, c);
if(s > 0)
{
v2.push_back({a, b, c});
mn += s;
cnt++;
}
if(cnt == node - 1)
break;
}
return mn;
}
int remst(int a, int b, int c)
{
for(int i=1; i<=node; i++)
parent[i] = -1;
int mn = 0, cnt = 0;
for(int i=0; i<v1.size(); i++)
{
if(v1[i].u == a && v1[i].v == b && v1[i].w == c)
continue;
int s = unions(v1[i].u, v1[i].v, v1[i].w);
if(s > 0)
{
mn += s;
cnt++;
}
if(cnt == node -1)
break;
}
return mn;
}
int main()
{
int t;
cin >> t;
while(t--)
{
int fnode, snode, weight;
cin >> node >> edge;
for(int i=1; i<= edge; i++)
{
cin >> fnode >> snode >> weight;
v1.push_back({fnode, snode, weight});
}
sort(v1.begin(), v1.end(), compare);
int cnt = mst();
for(int i=0; i<v2.size(); i++)
{
int a = v2[i].u;
int b = v2[i].v;
int c = v2[i].w;
int p = remst(a, b, c);
if(p > 0)
v3.push_back(p);
}
sort(v3.begin(), v3.end());
int p;
for(int i=0;i<v3.size();i++)
{
if(cnt <= v3[i])
{
p = v3[i];
break;
}
}
cout << cnt << " " << p << "\n";
v1.clear();
v2.clear();
v3.clear();
for(int i=0;i<300;i++)
parent[i] = 0;
}
return 0;
}
Comments
Post a Comment