此题关于并查集
查看原帖
此题关于并查集
307483
苏黎世楼主2020/10/12 19:38

为什么这题不可以用并查集来做呢亲测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;
}
2020/10/12 19:38
加载中...