uvalive 4848 Tour Belt

题意：

一个KTO被定义为一个特殊的连通块，这个连通块满足一个要求，这个连通块中的最短的边大于与这个连通相连的不属于这个连通块的边中的最大值。

给出一个图，统计KTO里面的点有多少个。（一个点可以属于多个KTO）

如a中有3个KTO，b中有6个KTO。

思路：

因为题目中给出的n最大为5000，那么相应的边为25000000，数量太大，所以一直卡在如何O(log(m))的计算连通块的数量。

但是看了题解之后，大家都是暴力的，那么以后有暴力思路就写(T)一发暴力好了。

首先把边从大到小排序，对于每一条边的两个点，如果已经在同一个连通块中，那么就不管了，因为已经统计过这个连通块了；

若不在同一个连通块中，则合并这个两个连通块，然后判断是否满足条件，若满足条件，那么就加上合并后连通块中的总共有的点数。

重点就是如何判断满足条件以及统计连通块中的点的个数。

首先，这个条件是指连通块中的最小的边必须大于与连通块相连的但不属于连通块的最大的边，当前枚举到的边，一定大于或者等于与连通块相连的但不属于连通块的最大的边，因为边是按照从大到小排序的，所以更大的边已经合并到连通块中；但是当前枚举的边却不一定是连通块中的最小的边，因为可能后面更小的边的两个点都在当前的连通块中，写题的时候就是在这里WA的。

解决办法当然就是暴力从当前边开始枚举，往后找在连通块中的最小的边，以及不在连通块当中的最大的边，比较两者的值即可。

第二个问题是统计连通块中的点的数量。感谢MZjj点拨本弱带权并查集，因为是启发式合并，所以就像按秩合并那样开一个数组记录一下size就可以了，脑子太迟钝Orz。

代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <iostream>
  6 using namespace std;
  7 
  8 const int N = 5005;
  9 const int inf = 0x3f3f3f3f;
 10 
 11 struct edge
 12 {
 13     int x,y;
 14     int c;
 15     
 16     edge(int aa,int bb,int cc)
 17     {
 18         x = aa;
 19         y = bb;
 20         c = cc;
 21     }
 22 };
 23 
 24 vector<edge> es;
 25 int par[N],sz[N];
 26 
 27 void init(int n)
 28 {
 29     es.clear();
 30     
 31     for (int i = 0;i <= n;i++)
 32     {
 33         par[i] = i;
 34         sz[i] = 1;
 35     }
 36 }
 37 
 38 bool cmp(edge ea,edge eb)
 39 {
 40     return ea.c > eb.c;
 41 }
 42 
 43 int fin(int x)
 44 {
 45     if (x == par[x]) return x;
 46     else return par[x] = fin(par[x]);
 47 }
 48 
 49 void unit(int x,int y)
 50 {
 51     x = fin(x);
 52     y = fin(y);
 53     
 54     if (x == y) return;
 55     
 56     par[x] = y;
 57     sz[y] += sz[x];
 58 }
 59 
 60 int main()
 61 {
 62     int t;
 63     
 64     scanf("%d",&t);
 65     
 66     while (t--)
 67     {
 68         int n,m;
 69         
 70         scanf("%d%d",&n,&m);
 71         
 72         init(n);
 73         
 74         for (int i = 0;i < m;i++)
 75         {
 76             int a,b,c;
 77             
 78             scanf("%d%d%d",&a,&b,&c);
 79             
 80             es.push_back(edge(a,b,c));
 81         }
 82         
 83         sort(es.begin(),es.end(),cmp);
 84         
 85         long long ans = 0;
 86         
 87         for (int i = 0;i < es.size();i++)
 88         {
 89             int x = es[i].x,y = es[i].y;
 90             
 91             if (fin(x) == fin(y)) continue;
 92             
 93             unit(x,y);
 94             
 95             int maxn = -inf,minn = inf;
 96             
 97             for (int j = i;j < es.size();j++)
 98             {
 99                 int p = es[j].x,q = es[j].y;
100                 
101                 if (fin(p) == fin(q) && fin(p) == fin(x))
102                 {
103                     minn = min(minn,es[j].c);
104                 }
105                 else if (fin(p) == fin(x) || fin(q) == fin(x))
106                 {
107                     if (fin(p) != fin(q))
108                     {
109                         maxn = max(maxn,es[j].c);
110                     }
111                 }
112             }
113             
114             if (minn > maxn)
115                 ans += sz[fin(x)];
116                 
117             //if (sz[fin(x)] == 6) printf("%d %d **
",maxn,minn);
118         }
119         
120         cout << ans << endl;
121     }
122     
123     return 0;
124 }