【HDOJ3047】Zjnu Stadium（带权并查集）

题意：浙江省第十二届大学生运动会在浙江师范大学举行，为此在浙师大建造了一座能容纳近万人的新体育场。
观众席每一行构成一个圆形，每个圆形由300个座位组成，对300个座位按照顺时针编号1到300,且可以认为有无数多行。现在比赛的组织者希望观众进入场地的顺序可以更加的有趣，在门票上并没有规定每个人的座位，而是与这个圈中某个人的相对位置，可以坐在任意一行。
门票上标示的形式如下：A B x 表示第B个人必须在A的顺时针方向x个位置（比如A坐在4号位子，x=2，则B必须坐在6号位子）。
现在你就座位志愿者在入场口检票。如果拿到一张门票，与之前给定的矛盾，则被视为是假票，如果无矛盾，视为真票。现在给定该行入场观众的顺序，以及他们手中的门票，请问其中有多少假票？

第一行两个数N(1<=N<=50,000)和m(1<=m<=100,000)。表示N个人，m张票。

思路：复习下带权并查集的模板

dis[x]代表路径压缩后到根结点的距离

合并集合时新的dis可以使用向量运算求出

 var f,dis:array[..]of longint;

     n,m,i,u,v,x,y,z,ans:longint;

 function find(k:longint):longint;

 var x:longint;

 begin

  if k=f[k] then exit(k);

  x:=f[k];

  f[k]:=find(f[k]);

  dis[k]:=(dis[k]+dis[x]) mod ;

  exit(f[k]);

 end;

 procedure union(x,y,z:longint);

 var u,v:longint;

 begin

  u:=find(x); v:=find(y);

  f[v]:=u;

  dis[v]:=(dis[x]+z-dis[y]+) mod ;

 end;

 begin

  assign(input,'hdoj3047.in'); reset(input);

  assign(output,'hdoj3047.out'); rewrite(output);

  while not eof do

  begin

   readln(n,m);

   if (n=)and(m=) then break;

   ans:=;

   for i:= to n do

   begin

    f[i]:=i; dis[i]:=;

   end;

   for i:= to m do

   begin

    readln(x,y,z);

    u:=find(x); v:=find(y);

    if u<>v then union(x,y,z)

     else if (dis[x]+z) mod <>dis[y] then inc(ans);

   end;

   writeln(ans);

  end;

  close(input);

  close(output);

 end.

UPD（2018.10.18）：C++

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   61000

 #define M   6100000

 #define eps 1e-8

 #define pi  acos(-1)

 #define oo  1e9

 int f[N],dis[N];

 int find(int k)

 {

     if(k==f[k]) return k;

     int x=f[k];

     f[k]=find(f[k]);

     dis[k]=(dis[k]+dis[x])%;

     return f[k];

 }

 void Union(int x,int y,int z)

 {

     int u=find(x);

     int v=find(y);

     f[v]=u;

     dis[v]=(dis[x]+z-dis[y]+)%;

 }

 int main()

 {

     //freopen("hdoj3047.in","r",stdin);

     //freopen("hdoj3047.out","w",stdout);

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         int ans=;

         memset(dis,,sizeof(dis));

         for(int i=;i<=n;i++) f[i]=i;

         for(int i=;i<=m;i++)

         {

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             int u=find(x);

             int v=find(y);

             if(u!=v) Union(x,y,z);

              else if((dis[x]+z)%!=dis[y]) ans++;

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

【HDOJ3047】Zjnu Stadium（带权并查集）

最新文章

热门文章