hdu 3047 Zjnu Stadium（加权并查集）2009 Multi-University Training Contest 14

题意：

有一个运动场，运动场的坐席是环形的，有1~300共300列座位，每列按有无限个座位计算T_T。

输入：

有多组输入样例，每组样例首行包含两个正整数n, m。分别表示共有n个人，m次操作。

接下来m行，每行包含a, b, x三个整数，表示a在b右边x个位置。

输出：

如果a，b的关系已经存在，新操作如果获得的位置关系与已存在的关系不同，则ans+1。输出ans，每组输出占一行。

用加权并查集可以解决。权值存在val[]数组里，val[i]的含义为从i到根节点的距离。

由于是一个长度为300的环形座位，所以每次算得的结果都需要mod 300（然而实际上不mod 300也可以ac）。

具体见代码——

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N = ;

 const int M = ;

 int fm[N], val[N];

 int a, b, x;

 int n, m;

 int ans;

 void init()

 {

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

     {

         fm[i] = i;

         val[i] = ;

     }

     ans = ;

 }

 int mfind(int x)

 {

     if(x == fm[x]) return x;

     int t = fm[x];

     fm[x] = mfind(fm[x]);

     val[x] += val[t];

     val[x] %= M;

     return fm[x];

 }

 void mmerge()

 {

     int fx = mfind(a);

     int fy = mfind(b);

     if(fx != fy)

     {

         fm[fx] = fy;

         val[fx] += val[b]-val[a]+x;             //由于需要获得的是从fx到fy的距离，所以需要以b与a的相对距离再加上x

         val[fx] %= M;

     }

     else

     {

         if((val[a]-val[b]+M)%M != x%M) ans++;

     }

 }

 void work()

 {

     while(m--)

     {

         scanf("%d%d%d", &a, &b, &x);

         mmerge();

     }

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

 }

 int main()

 {

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

     while(~scanf("%d%d", &n, &m))

     {

         init();

         work();

     }

     return ;

 }

巴特西

hdu 3047 Zjnu Stadium（加权并查集）2009 Multi-University Training Contest 14

最新文章

热门文章