首页 > 代码库 > 【BZOJ】1202: [HNOI2005]狡猾的商人

【BZOJ】1202: [HNOI2005]狡猾的商人

2024-08-30 00:44:45   217人阅读

【算法】并查集

【题解】

由于存在负数，判断信息合法性的途径只有多个已知区间能组成一个已知大区间。

用并查集维护已知区间，每次将(x-1,y)连边，就把这两个端点送入并查集，后面如果需要合法性判断时就要必然会访问到他们之一。

每次的读入v相当于v[y]-v[x-1]，维护并查集每个节点到其根的距离。

连边涉及并查集的合并时，即fa[fa[x-1]]=fa[y]时，要更新fa[x-1]的距离(原为0)为到新根fa[y]的距离，注意前缀和的方向问题就能得出计算式。

最后，注意find过程中更新距离时必须严格按照以下过程执行：

int t=find(fa[x]);

d[x]+=d[fa[x]];

fa[x]=t;

这是维护并查集距离的常用套路。

不明白本蒟蒻口胡的可以左转：http://blog.csdn.net/cjk_cjk/article/details/46681371

技术分享 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int fa[maxn],d[maxn];
int n,m,T;
int find(int x)
{
    if(fa[x]==x)return x;
    int t=find(fa[x]);
    d[x]+=d[fa[x]];
    fa[x]=t;
    return fa[x];
}
int main()
{
    scanf("%d",&T);
    while(T--)
     {
         memset(d,0,sizeof(d));
         scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)fa[i]=i;
         bool flag=0;
         for(int i=1;i<=m;i++)
          {
              int x,y,w;
              scanf("%d%d%d",&x,&y,&w);
              x--;
              int p=find(x),q=find(y);
              if(p!=q)
               {
                   fa[p]=q;
                   d[p]=d[y]-(d[x]+w);//注意前缀和方向 
               }
              else if(d[y]-d[x]!=w){flag=1;break;}
          }
         if(flag)printf("false\n");else printf("true\n");
     }
    return 0;
}
View Code

 

【BZOJ】1202: [HNOI2005]狡猾的商人


联系
我们