社区讨论
40/60 分求调
P1991无线通讯网参与者 2已保存回复 8
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mhj34n8d
- 此快照首次捕获于
- 2025/11/03 19:57 4 个月前
- 此快照最后确认于
- 2025/11/03 19:57 4 个月前
如果这样是 40 分（）：
CPP#include <bits/stdc++.h>
using namespace std;
int S;
int P;
int t = 0;
struct edge
{
int u;
int v;
double w;
inline bool operator<(const edge &other) const
{
return this->w < other.w;
}
// inline constexpr edge(edge &&) noexcept = default;
// inline constexpr edge & operator=(edge &&) noexcept = default;
};
struct pos
{
int x;
int y;
inline double operator-(const pos &other) const
{
return std::sqrt(((this->x - other.x) * (this->x - other.x)) + ((this->y - other.y) * (this->y - other.y)));
}
// inline constexpr pos(pos &&) noexcept = default;
// inline constexpr pos & operator=(pos &&) noexcept = default;
};
std::vector<pos, std::allocator<pos>> p = std::vector<pos, std::allocator<pos>>();
std::vector<edge, std::allocator<edge>> edges = std::vector<edge, std::allocator<edge>>();
double kruskal(const std::vector<edge, std::allocator<edge>> &edges, const int &maxm, const int &n)
{
std::vector<int, std::allocator<int>> f = std::vector<int, std::allocator<int>>(static_cast<unsigned long>(n + 1), std::allocator<int>());
for (int i = 1; i <= n; ++i)
{
f.operator[](i) = i;
}
class __lambda_29_28
{
public:
inline int operator()(int x) const
{
if (f.operator[](x) == x)
{
return x;
}
return f.operator[](x) = find.operator()(f.operator[](x));
}
private:
std::vector<int, std::allocator<int>> &f;
std::function<int(int)> &find;
public:
// inline /*constexpr */ __lambda_29_28(const __lambda_29_28 &) noexcept = default;
// inline /*constexpr */ __lambda_29_28(__lambda_29_28 &&) noexcept = default;
__lambda_29_28(std::vector<int, std::allocator<int>> &_f, std::function<int(int)> &_find)
: f{_f}, find{_find}
{
}
};
std::function<int(int)> find = std::function<int(int)>(std::function<int(int)>(__lambda_29_28{f, find}));
double s = 0;
int m = 0;
for (int i = 0; static_cast<unsigned long>(i) < edges.size(); ++i)
{
int u = find.operator()(edges.operator[](i).u);
int v = find.operator()(edges.operator[](i).v);
if (u != v)
{
f.operator[](u) = v;
if (++m == maxm)
{
break;
}
s = edges.operator[](i).w;
}
}
return s;
}
int main()
{
std::ios_base::sync_with_stdio(false);
static_cast<std::basic_ios<char> &>(std::cin).tie(0);
std::cin.operator>>(S).operator>>(P);
for (int i = 1; i <= P; ++i)
{
int x;
int y;
std::cin.operator>>(x).operator>>(y);
p.push_back(pos{x, y});
}
for (int i = 1; i <= P; ++i)
{
for (int j = 1; j <= P; ++j)
{
if (i != j)
{
edges.push_back(edge{i, j, p.operator[](i).operator-(p.operator[](j))});
}
}
;
}
std::sort(__gnu_cxx::__normal_iterator<edge *, std::vector<edge, std::allocator<edge>>>(edges.begin()), __gnu_cxx::__normal_iterator<edge *, std::vector<edge, std::allocator<edge>>>(edges.end()));
std::operator<<(std::operator<<(std::cout.operator<<(std::fixed), std::_Setprecision(std::setprecision(2))).operator<<(kruskal(edges, P - S, P)), '\n');
return 0;
}
但是如果这样，就成了 60 分（）：
CPP#include <bits/stdc++.h>
using namespace std;
int S;
int P;
int t = 0;
struct edge
{
int u;
int v;
double w;
inline bool operator<(const edge &other) const
{
return this->w < other.w;
}
// inline constexpr edge(edge &&) noexcept = default;
// inline constexpr edge & operator=(edge &&) noexcept = default;
};
struct pos
{
int x;
int y;
inline double operator-(const pos &other) const
{
return std::sqrt(((this->x - other.x) * (this->x - other.x)) + ((this->y - other.y) * (this->y - other.y)));
}
// inline constexpr pos(pos &&) noexcept = default;
// inline constexpr pos & operator=(pos &&) noexcept = default;
};
std::vector<pos, std::allocator<pos>> p = std::vector<pos, std::allocator<pos>>();
std::vector<edge, std::allocator<edge>> edges = std::vector<edge, std::allocator<edge>>();
double kruskal(const std::vector<edge, std::allocator<edge>> &edges, const int &maxm, const int &n)
{
std::vector<int, std::allocator<int>> f = std::vector<int, std::allocator<int>>(static_cast<unsigned long>(n + 1), std::allocator<int>());
for (int i = 1; i <= n; ++i)
{
f.operator[](i) = i;
}
class __lambda_29_28
{
public:
inline int operator()(int x) const
{
if (f.operator[](x) == x)
{
return x;
}
return f.operator[](x) = find.operator()(f.operator[](x));
}
private:
std::vector<int, std::allocator<int>> &f;
std::function<int(int)> &find;
public:
// inline /*constexpr */ __lambda_29_28(const __lambda_29_28 &) noexcept = default;
// inline /*constexpr */ __lambda_29_28(__lambda_29_28 &&) noexcept = default;
__lambda_29_28(std::vector<int, std::allocator<int>> &_f, std::function<int(int)> &_find)
: f{_f}, find{_find}
{
}
};
std::function<int(int)> find = std::function<int(int)>(std::function<int(int)>(__lambda_29_28{f, find}));
double s = 0;
int m = 0;
for (int i = 0; static_cast<unsigned long>(i) < edges.size(); ++i)
{
int u = find.operator()(edges.operator[](i).u);
int v = find.operator()(edges.operator[](i).v);
if (u != v)
{
f.operator[](u) = v;
s = edges.operator[](i).w;
if (++m == maxm)
{
break;
}
}
}
return s;
}
int main()
{
std::ios_base::sync_with_stdio(false);
static_cast<std::basic_ios<char> &>(std::cin).tie(0);
std::cin.operator>>(S).operator>>(P);
for (int i = 1; i <= P; ++i)
{
int x;
int y;
std::cin.operator>>(x).operator>>(y);
p.push_back(pos{x, y});
}
for (int i = 1; i <= P; ++i)
{
for (int j = 1; j <= P; ++j)
{
if (i != j)
{
edges.push_back(edge{i, j, p.operator[](i).operator-(p.operator[](j))});
}
}
;
}
std::sort(__gnu_cxx::__normal_iterator<edge *, std::vector<edge, std::allocator<edge>>>(edges.begin()), __gnu_cxx::__normal_iterator<edge *, std::vector<edge, std::allocator<edge>>>(edges.end()));
std::operator<<(std::operator<<(std::cout.operator<<(std::fixed), std::_Setprecision(std::setprecision(2))).operator<<(kruskal(edges, P - S, P)), '\n');
return 0;
}
两种的区别：
DIFF--- 版本1.cpp
+++ 版本2.cpp
@@ -76,12 +76,11 @@
if (u != v)
{
f.operator[](u) = v;
+ s = edges.operator[](i).w;
if (++m == maxm)
{
break;
}
-
- s = edges.operator[](i).w;
}
}
回复
共 8 条回复，欢迎继续交流。
正在加载回复...