也不能叫做发现了错误,但是找到了有问题的位置(这其实不是我代码,是我拿别的AC代码魔改的,把排序改成我的写法就挂了)。
原本能AC的代码是把和1相连的与不和1相连的分开来,然后按照边权排序。排序函数:return w < b.w;
可以 AC。我只把排序函数改成:
bool operator<(node b)
{
if(w!=b.w)
return w < b.w;
return (x==1||y==1)>(b.x==1||b.y==1);
}
就WA了,且最后一行不管是>
<
>=
<=
都会WA。
有人看看什么原因吗!!?拜谢!!!!
完整 AC 代码:(按上述方法改了比较函数就 WA)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &x)
{
x = 0;
char c = getchar(), f = 0;
for (; c < 48 || c > 59; c = getchar())
if (!(c ^ 45))
f = 1;
for (; c >= 48 && c <= 57; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
f ? x = -x : 0;
}
struct node
{
int x, y;
double w;
int id;
bool operator<(node b)
{
// if(w!=b.w)
return w < b.w;
// return (x==1||y==1)>=(b.x==1||b.y==1);
}
} e[100005], e1[100005], e2[100005],bk[100005];
int n, m, K, fa[10005], t1, t2;
inline int getf(int x) { return fa[x] == x ? x : fa[x] = getf(fa[x]); }
inline char mrg(int x, int y)
{
x = getf(x), y = getf(y);
if (x ^ y)
return fa[x] = y, 1;
else
return 0;
}
// ↑并查集
inline char check(ll w)
{
int cnt = 0;
memcpy(e,bk,sizeof bk);
for(int i=1;i<=m;i++)
if(e[i].x==1||e[i].y==1)
e[i].w+=w / 10000.0;
sort(e + 1, e + m + 1);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++)
if (mrg(e[i].x, e[i].y))
cnt += (e[i].x == 1 || e[i].y == 1);
for(int i=1;i<=m;i++)
if(e[i].x==1||e[i].y==1)
e[i].w-=w / 10000.0;
return cnt <= K; // 计算有多少个点与 1 相连
} // ↑二分check函数
int main()
{
read(n), read(m), read(K);
ll le = -1e9 - 7, ri = 1e9 + 7; // 值域,尽量大
for (int i = 1, x, y, w; i <= m; i++)
{
read(x), read(y), read(w);
if (x == 1 || y == 1)
e1[++t1] = (node){x, y, w, i};
else
e2[++t2] = (node){x, y, w, i};
// e[i]={x,y,w,i};
}
for (int i = 1; i <= t1; i++)
e[i] = e1[i];
for (int i = 1; i <= t2; i++)
e[i + t1] = e2[i];
memcpy(bk,e,sizeof e);
// ↑把边分类 ↓wqs二分主体(一行
while (le < ri)
{
ll md = (le + ri) >>1;
if (check(md))
ri = md ;
else
le = md + 1;
}
if (!check(ri))
return puts("-1"), 0;
else
printf("%d\n", n - 1);
memcpy(e,bk,sizeof bk);
for(int i=1;i<=m;i++)
if(e[i].x==1||e[i].y==1)
e[i].w+=ri / 10000.0;
sort(e + 1, e + m + 1);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++)
if (mrg(e[i].x, e[i].y))
printf("%d ", e[i].id);
return putchar('\n'), 0; // ↑输出方案,check 直接赋值一遍(
}