正文 

当前位置： 首页 > java > java教程

hdu6109数据分割并查集（2017"百度之星"程序设计大赛-初赛（a））

Coolxxx Coolxxx     2022-09-14     505

关键词：

 

 

数据分割

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1119    Accepted Submission(s): 268


Problem Description
小w来到百度之星的赛场上，准备开始实现一个程序自动分析系统。

这个程序接受一些形如xi=xj 或 xi≠xj 的相等/不等约束条件作为输入，判定是否可以通过给每个 w 赋适当的值，来满足这些条件。

输入包含多组数据。
然而粗心的小w不幸地把每组数据之间的分隔符删掉了。
他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足的。

请帮助他恢复这些分隔符。
 

Input
第1行：一个数字L，表示后面输入的总行数。

之后L行，每行包含三个整数，i,j,e，描述一个相等/不等的约束条件，若e=1，则该约束条件为xi=xj ，若e=0，则该约束条件为 xi≠xj 。

i,j,L≤100000

xi,xj≤L
 

Output
输出共T+1行。

第一行一个整数T，表示数据组数。

接下来T行的第i行，一个整数，表示第i组数据中的约束条件个数。
 

Sample Input
6 2 2 1 2 2 1 1 1 1 3 1 1 1 3 1 1 3 0
 

Sample Output
1 6
 

Source
2017"百度之星"程序设计大赛 - 初赛（A）
 

Recommend
liuyiding   |   We have carefully selected several similar problems for you:  6113 6112 6111 6110 6109 
 

Statistic | Submit | Discuss | Note

 

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=6109

题目大意：

　　给一些等式或不等式，xi=xj或xi!=xj，求一个划分，使得每一部分内的等式组去掉最后一个式子后成立。

题目思路：

　　【并查集】

　　将每个Xi拆成Xi和~Xi，若等式成立则将Xi和Xj并，~Xi和~Xj并，否则将Xi和~Xj并，~Xi和Xj并。出现矛盾则划分。

 

技术分享 
 1 /****************************************************
 2 
 3     Author : Coolxxx
 4     Copyright 2017 by Coolxxx. All rights reserved.
 5     BLOG : http://blog.csdn.net/u010568270
 6 
 7 ****************************************************/
 8 #include<bits/stdc++.h>
 9 #pragma comment(linker,"/STACK:1024000000,1024000000")
10 #define abs(a) ((a)>0?(a):(-(a)))
11 #define lowbit(a) (a&(-a))
12 #define sqr(a) ((a)*(a))
13 #define mem(a,b) memset(a,b,sizeof(a))
14 const double EPS=0.00001;
15 const int J=10;
16 const int MOD=100000007;
17 const int MAX=0x7f7f7f7f;
18 const double PI=3.14159265358979323;
19 const int N=100004;
20 const int M=1004;
21 using namespace std;
22 typedef long long LL;
23 double anss;
24 LL aans;
25 int cas,cass;
26 int n,m,lll,ans;
27 int fa[N+N];
28 int sz[N];
29 int zhao(int aa)
30 {
31     if(fa[aa]==aa)return aa;
32     return fa[aa]=zhao(fa[aa]);
33 }
34 int main()
35 {
36     #ifndef ONLINE_JUDGE
37     freopen("1.txt","r",stdin);
38 //    freopen("2.txt","w",stdout);
39     #endif
40     int i,j,k;
41     int x,y,z;
42 //    for(scanf("%d",&cass);cass;cass--)
43 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
44     while(~scanf("%d",&n))
45     {
46         lll=0;sz[0]=0;k=0;
47         for(i=1;i<=n;i++)
48             fa[i]=i,fa[i+n]=i+n;
49         for(i=1;i<=n;i++)
50         {
51             scanf("%d%d%d",&x,&y,&z);
52             k=max(k,x);
53             k=max(k,y);
54             int fx=zhao(x);
55             int fy=zhao(y);
56             int ax=zhao(x+n);
57             int ay=zhao(y+n);
58             if(z)
59             {
60                 if(fx==ay || fy==ax)
61                 {
62                     sz[++lll]=i;
63                     for(j=1;j<=k;j++)
64                         fa[j]=j,fa[j+n]=j+n;
65                     k=0;
66                 }
67                 else 
68                 {
69                     fa[fy]=fx;
70                     fa[ay]=ax;
71                 }
72             }
73             else
74             {
75                 if(fx==fy || ax==ay)
76                 {
77                     sz[++lll]=i;
78                     for(j=1;j<=k;j++)
79                         fa[j]=j,fa[j+n]=j+n;
80                     k=0;
81                 }
82                 else 
83                 {
84                     fa[ay]=fx;
85                     fa[ax]=fy;
86                 }
87             }
88         }
89         printf("%d
",lll);
90         for(i=1;i<=lll;i++)
91             printf("%d
",sz[i]-sz[i-1]);
92     }
93     return 0;
94 }
95 /*
96 //
97 
98 //
99 */
View Code

 
































hdu6109(并查集+set/倍增)

...cn/showproblem.php?pid=6109分析　　对于相同的条件，明显直接并查集　　对于不同的条件，可以用set来保存，并查集合并的时候也要对set启发式合并　　还有另一种很奇妙的做法　　如果我们只考虑一段[l..r]是否可行，那么我们可以... 查看详情

hdu6109数据分割(代码片段)

...每个w赋适当的值，来满足这些条件。 输入包含多组数据。 然而粗心的小w不幸地把每组数据之间的分隔符删掉了。 他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足... 查看详情

2017"百度之星"程序设计大赛-初赛（a）数据分割

n<=100000条相等/不等关系描述<=100000个数，把这些数据分割成若干段使得每一段描述都出现冲突且冲突只出现在最后一行。相等关系具有传递性，并查集维护；不等关系根据相等关系进行合并，采用平衡树的启发式合并。每次... 查看详情

hdu6074[并查集+lca+思维]2017多校4

...数。下面是过程分析。过程中一共运用了两个并查集。[数据]1103121324253637485951096315014252091081040[分析]首先我们将图构建出来我们将m次询问按权值从小到 查看详情

hdu3938并查集

求小于L的路径点对数（路上的最大值），按权值排序，从小到大并查集建图，有点kruskal的意思。/**@Date:2017-09-2217:30:11*@FileName:HDU3938并查集离线.cpp*@Platform:Windows*@Author:Lweleth([email protected])*@Link:https://github.com/*@Version:$Id$ 查看详情

hdu_3038_并查集

...了1，才能把一组组都串起来。注意，题目描述的是一组数据，但是实际是读到EOF。 #include<iostream>#include<cstring>#inclu 查看详情

hdu5652indiaandchinaorigins并查集

IndiaandChinaOrigins ProblemDescriptionAlongtimeagotherearenohimalayasbetweenIndiaandChina,thebothculturesarefrequentlyexchangedandarekeptinsyncatthattime,buteventuallyhimalayasriseup.Withthatatf 查看详情

并查集树数据结构hdu1325

我的解法就是去构造了一棵树以数组的存储方式数组的值存放节点的根。排除空树剩下的就是出现环和多根节点的情况也就是排除森林和有一个节点多个入度的情况排除森林就用到了并查集也就是便利数组让其仅仅有一个根排除... 查看详情

hdu3938(离线并查集)

...，有多少条路径（任意两点可到达的对数）题解：离线的并查集，刚开始的时候，暴力模拟，在每个并查集里边计算路径数目，果断T。。。正解：离线并查集，将每个查询保存起来，根 查看详情

hdu1213howmanytables（并查集）

传送门DescriptionTodayisIgnatius‘birthday.Heinvitesalotoffriends.Nowit‘sdinnertime.Ignatiuswantstoknowhowmanytablesheneedsatleast.Youhavetonoticethatnotallthefriendsknoweachother,andallthefriendsdonotwan 查看详情

hdu1856并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1856  MoreisbetterTimeLimit:5000/1000MS(Java/Others)    MemoryLimit:327680/102400K(Java/Others)TotalSubmission(s):29843 &nb 查看详情

*hdu3172并查集

VirtualFriendsTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):8165    AcceptedSubmission(s):2345ProblemDescription 查看详情

hdu1325并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1325 IsItATree?TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):26387   & 查看详情

*hdu1829并查集

ABug‘sLifeTimeLimit:15000/5000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):14121    AcceptedSubmission(s):4603ProblemDescriptionBa 查看详情

*hdu3047并查集

ZjnuStadiumTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):3062    AcceptedSubmission(s):1182ProblemDescriptionIn1 查看详情

hdu1325（并查集）

IsItATree?TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):23312    AcceptedSubmission(s):5338ProblemDescriptionAtr 查看详情

hdu4496并查集

http://acm.hdu.edu.cn/showproblem.php?pid=4496 D-CityTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):4802     查看详情

hdu_1232_并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1232 第一道并查集，挺好理解的，初始化，查找根节点，连接，路径压缩。 #include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intpre[1005],t[1005],n,m 查看详情