2022.11.17 第一次
错误代码, 错的经典。只要未用过的边和用过的边有相等的边,且用过的边的祖宗节点(排序后的序号即未用过的边的祖宗节点)等于最小生成树的祖宗节点我的代码就会错。
#include <iostream>
#iclude <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e2 +10, M = 1e4 + 10; // 开始这里写的 1e3 + 10,边和点没看清
int f[N], st[M];
int root(int x)
{
if (x != f[x]) f[x] = root(f[x]);
return f[x];
}
struct node
{
int x, y, w;
} a[M];
int cmp(node x, node y)
{
return x.w < y.w;
}
int main()
{
int t;
cin >> t;
while (t -- )
{
memset(st, 0, sizeof st); // 开始忘了这个, 虽然加上这个仍然不全对
vector<int>vec;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) f[i] = i;
for (int i = 1; i <= m; i ++ )
{
cin >> a[i].x >> a[i].y >> a[i].w;
}
sort(a + 1, a + m + 1, cmp);
int sum = 0;
for (int i = 1; i <= m; i ++ )
{
if (root(a[i].x) != root(a[i].y))
{
st[i] = 1;
sum += a[i].w;
vec.push_back(i); // vec 存原最小生成树里面的边在 a 中的下标
// 这里的 i 对应的边是排过序之后的边的下标, 难怪调试时不对劲,花了我不少时间
// 但加深了我的理解
f[root(a[i].x)] = root(a[i].y);
}
}
cout << "排序后边的情况:\n";
for (int i = 1; i <= m; i ++ ) cout << "a[i].x=" << a[i].x << ' ' << "a[i].y=" << a[i].y << ' ' << "a[i].w=" << a[i].w << '\n';
cout << '\n';
cout << "排序后被选中的边:\n";
for (int i = 0; i < vec.size(); i ++ )
{
cout << "vec[i]=" << vec[i] << ' ' << "a[vec[i]].w=" << a[vec[i]].w << '\n';
}
cout << "\n";
cout << "连边时被标记的边:\n";
for (int i = 1; i <= m; i ++ ) cout << "i=" << i << ' ' <<"st[i]=" << st[i] << '\n';
cout << "\n";
int flag = 1; // 1 代表唯一
for (int i = 0; i < vec.size(); i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if (st[j] == 0)
{
int rxj = root(a[j].x), ryj = root(a[j].y);
int rxi = root(a[vec[i]].x), ryi = root(a[vec[i]].y);
if (rxj == rxi && ryj == ryi && a[j].w == a[vec[i]].w)
{
cout << "rxj=" << rxj << ' ' << "ryj=" << ryj << ' ' << "ryi=" << ryi << ' ' << "rxi=" << rxi << '\n';
cout << "vec[i]=" << vec[i] << ' ' << "j=" << j << '\n';
flag = 0;
}
}
if (flag == 0) break;
}
if (flag == 0) break;
}
cout << "sum=" << sum << '\n';
if (flag == 1) cout << sum << '\n';
else cout << "Not Unique!\n";
}
return 0;
}
/*
1
5 9
4 3 3
3 5 1
1 5 1
2 3 5
1 4 5
4 5 2
5 2 3
3 1 5
1 2 5
*/
// my : Not Unique!
// answer : 7
/*
1
5 7
3 1 3
5 3 3
3 4 5
1 2 4
5 4 4
2 3 2
1 5 4
*/
// my : not not unique
// answer : 12
WA 你妈的一万发终于过了
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e2 +10, M = 1e4 + 10; // 开始这里写的 1e3 + 10,边和点没看清
int f[N], st[M];
int root(int x)
{
if (x != f[x]) f[x] = root(f[x]);
return f[x];
}
struct node
{
int x, y, w;
} a[M];
int cmp(node x, node y)
{
return x.w < y.w;
}
int main()
{
int t;
cin >> t;
while (t -- )
{
vector<int>vec;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) f[i] = i;
for (int i = 1; i <= m; i ++ )
{
cin >> a[i].x >> a[i].y >> a[i].w;
}
sort(a + 1, a + m + 1, cmp);
int sum = 0;
for (int i = 1; i <= m; i ++ )
{
if (root(a[i].x) != root(a[i].y))
{
sum += a[i].w;
vec.push_back(i); // vec 存原最小生成树里面的边在 a 中的下标
// 这里的 i 对应的边是排过序之后的边的下标, 难怪调试时不对劲,花了我不少时间
// 但加深了我的理解
f[root(a[i].x)] = root(a[i].y);
}
}
for (int i = 0; i < vec.size(); i ++ )
{
int sum_se = 0;
for (int j = 1; j <= n; j ++ ) f[j] = j;
for (int k = 1; k <= m; k ++ )
{
if (k == vec[i]) continue;
if (root(a[k].x) != root(a[k].y))
{
sum_se += a[k].w;
f[root(a[k].x)] = root(a[k].y);
}
}
if (sum_se == sum)
{
sum = -1;
break;
}
}
if (sum == -1) cout << "Not Unique!\n";
else cout << sum << '\n';
}
return 0;
}
/*
1
5 9
4 3 3
3 5 1
1 5 1
2 3 5
1 4 5
4 5 2
5 2 3
3 1 5
1 2 5
*/
// my : Not Unique!
// answer : 7
/*
1
5 7
3 1 3
5 3 3
3 4 5
1 2 4
5 4 4
2 3 2
1 5 4
*/
// my : not not unique
// answer : 12