hdu 6109 数据分割-白红宇

hdu 6109 数据分割

阅读量：5029 次

发布时间：2019-06-12

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

/** * 题目描述有点坑，勉强能读懂，大致意思，有多组约束条件。原本每组数据之间是有分界符号的 * 现在分界符号没了，让你找出原来每组数据多少个条件，并且告诉，每组的最后一个条件会使得与前面的 * 条件冲突。 *  * 解题思路：膜拜大佬的解法，并查集+set大法。a==b 的约束条件用并查集，a!=b的约束给这个集合建边。 * 代表这两个集合不等。本题时间复杂度不太会计算。这样总感觉极限数据会TLE。结果就AC了。很绝望！ * 提供一种解题思路吧，倍增感觉很厉害，目前不知道怎么写》》 */#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long LL;const int INF=2e9+1e8;const int MOD=1e9+7;const double eps=0.0000000001;void fre(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout);}#define MSET(a,b) memset(a,b,sizeof(a))const int maxn=1e5+10;int a[maxn],b[maxn],e[maxn],pre[maxn];set
                    
                     G[maxn];void init(int n) //清空并查集和set图{ for(int i=1;i<=n;i++) pre[i]=i,G[i].clear();}int F(int x){ return x==pre[x]?x:pre[x]=F(pre[x]);}int main(){ int n; while(scanf("%d",&n)!=EOF) { vector
                     
                      ans; init(n); int sz=0; for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&e[i]); for(int i=1;i<=n;i++) { sz++; int x=F(a[i]),y=F(b[i]); if(e[i]) //如果是 a==b { if(x==y) continue;//a，b在同一个集合，a==b成立，不管。 else { if(G[x].find(y)!=G[x].end()) //a==b； a，b不在一个集合，存在边说明两个集合不等，显然不成立；统计答案 { ans.push_back(sz); sz=0; init(n); } else // a==b； a，b不在一个集合，a，b所在的集合不存在边，成立； { set
                      
                       ::iterator it; for(it=G[x].begin();it!=G[x].end();it++) //合并set， //意思是：将与x相连的边删掉，让他们和y相连 { G[y].insert(*it); G[*it].erase(x); G[*it].insert(y); } G[x].clear(); pre[x]=y; } } } else // 判断 a!=b { if(x==y) // a！=b ，a，b同在一个集合，不成立； { ans.push_back(sz); sz=0; init(n); } else G[x].insert(y),G[y].insert(x);//a！=b，a，b不在同一个集，两集合之间建边； } } printf("%d\n",(int)ans.size()); for(int i=0;i<(int)ans.size();i++) printf("%d\n",ans[i]); } return 0;}/**************************************************//** Copyright Notice **//** writer: wurong **//** school: nyist **//** blog : http://www.cnblogs.com/coded-ream/ **//**************************************************/