为什么这题不可以用并查集来做呢亲测10分
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxm = 20000;
int n, m, s, t, d, vtop, vis[maxm];
bool can[maxm];
struct node
{
int u, v, w;
friend bool operator < (const node a,const node b)
{
return a.w < b.w ;
}
};
struct ufs
{
int f[maxm];
ufs()
{
for(int i = 0;i <= maxm; ++i)
f[i] = i;
}
int fd(int x)
{
if(f[x] != x)
return f[x] = fd(f[x]);
return x;
}
void uni(int x, int y)
{
x = fd(x);
y = fd(y);
f[y] = x;
}
bool ask(int x, int y)
{
return fd(x) == fd(y) ;
}
};
ufs bin;
node a[maxm];
void cini()
{
scanf("%d%d",&n,&m);
for(int i = 0;i < m; ++i)
scanf("%d%d%d",&a[i].u, &a[i].v, &a[i].w);
sort(a, a + m);
scanf("%d", &d);
int x, y;
for(int i = 0;i < d; ++i)
{
scanf("%d%d", &x, &y);
for(int j = 0;j < m; ++j)
if(a[j].u == x && a[j].v ==y && can[j] == 0)
{
can[j] = 1;
vis[++vtop] = j;
break;
}
}
for(int i = 0;i < m; ++i)
if(!can[i])
bin.uni(a[i].u, a[i].v);
scanf("%d%d", &s, &t);
}
void work()
{
int ans = 0;
if(vtop)
{
for(int i = 1;i <= vtop; ++i)
{
if(bin.ask(s, t)) break;
bin.uni(a[vis[i]].u,a[vis[i]].v);
ans += a[vis[i]].w;
}
}
/* if( bin.ask(s, t) == false)
{
for(int i = 0;i < m; ++i)
if( !bin.ask(s, t))
{
bin.uni(a[i].u, a[i].v);
ans += a[i].w;
}else break;
}
*/
printf("%d", ans);
}
int main()
{
cini();
work();
return 0;
}