BZOJ 1202 狡猾的商人(带权并查集)-白红宇

BZOJ 1202 狡猾的商人(带权并查集)

阅读量：4619 次

发布时间：2019-06-09

本文共 1575 字，大约阅读时间需要 5 分钟。

给出了l,r,w。我们就得知了s[r]-s[l-1]=w.也就是说，点l-1和点r的距离为w。

于是可以使用带权并查集，定义dis[i]表示点i到根节点的距离。查询和合并的时候维护一下就OK了。

如果账本有错误，那么这两点的距离一定不等于在并查集上面的距离。

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-3# define MOD 100000007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                 
                   PII;typedef vector
                  
                    VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=10005;//Code begin...int fa[105], dis[105];int find(int x){ int tmp; if (fa[x]!=x) { tmp=find(fa[x]); dis[x]+=dis[fa[x]]; fa[x]=tmp; } return fa[x];}int main (){ int n, m, T, l, r, w; scanf("%d",&T); while (T--) { mem(dis,0); int flag=1; scanf("%d%d",&n,&m); FOR(i,0,n) fa[i]=i; while (m--) { scanf("%d%d%d",&l,&r,&w); if (!flag) continue; int u=find(l-1), v=find(r); if (u!=v) { dis[u]=dis[r]+w-dis[l-1]; fa[u]=v; } else { if (dis[l-1]-dis[r]!=w) flag=0; } } puts(flag?"true":"false"); } return 0;}