uva 1160 - X-Plosives

末蓝、 2021-12-16 19:05 173阅读 0赞

/\*  
题意：往仓库里放\*\*\*，把关键引爆\*\*\*的数对拿出并计数  
数学模型：输入数对，判断是否成环eg（1,2 2,3 3,4, 1,4）这个时候要计数。  
该题中让人费解反复的的是n种材料是不是都出现才会引爆？不是  
eg（1,2 2,4 1,4）也要累加计数。  
核心算法：并查集、判环 前面的数和当前的这个数只要都是一个根节点时就判为环 否则归并  
为一个集合一个根节点-1止。  
输入时候注意：循环输入EOF，开始时用了while(1)超时了没有节制注意一下  
Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu)  
:: Chapter 3. Data Structures :: Fundamental Data Structures :: Examples  
\*/  
//AC不容易  
\#include<stdio.h>  
\#include<string.h>  
const int M=100010;//100000+10;  
int ct;  
int fa\[M\];  
void inist()  
\{  
int i;  
for(i=0;i<M;i++)  
fa\[i+1\]=i+1;  
\}  
int find(int x)//查根节点  
\{  
while(fa\[x\]!=x)  
x=fa\[x\];  
return x ;  
//else return x;  
\}  
void Union(int a,int b)//并查集  
\{  
int i,j,k;  
int f1,f2;  
f1=find(a);  
f2=find(b);  
if(f1!=f2)  
\{  
fa\[f1\]=fa\[f2\];  
\}  
else ct++;  
\}  
int main()  
\{  
int a,b;  
while(scanf("%d",&a)!=EOF)//此处必须EOF的方式处理  
//不然就会判定为超时！！！  
\{  
ct=0;  
inist();//初始化所有根节点  
while(a!=-1)  
\{  
scanf("%d",&b);//if(a==-1)break;  
Union(a,b);//并查集  
scanf("%d",&a);  
\}  
printf("%d\\n",ct);  
\}  
return 0;  
\}  
/\*  
int main()  
\{  
int a,b;  
while(1)  
\{  
ct=0;  
inist();//初始化根节点  
while(1)//超时！！！！  
\{  
  
scanf("%d",&a);  
if(a==-1)break;  
scanf("%d",&b);  
Union(a,b);  
\}  
printf("%d\\n",ct);  
  
\}  
return 0;  
\}//\*/

转载于:https://www.cnblogs.com/someonelikeyou/archive/2013/02/19/2916902.html

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 codevs1160 蛇形矩阵

题目描述 Description 小明玩一个数字游戏，取个n行n列数字矩阵（其中n为不超过100的奇数），数字的填补方法为：在矩阵中心从1开始以逆时针方向绕行，逐圈扩大，直到

冷不防/ 2024年02月17日 23:17/ 0 赞/ 76 阅读

相关 leetcode1160. 拼写单词

题目描述：给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某

迷南。/ 2023年07月16日 03:55/ 0 赞/ 14 阅读

相关 pku 1160 Post Office

\include <iostream> \include <cmath> \include <climits> using namespace std; int pos\[30

亦凉/ 2022年08月13日 16:49/ 0 赞/ 112 阅读

相关 UVA 1160——X-Plosives

题意：给定一些化合物（含有两个元素），当满足k个化合物且有k个元素的时候会发生爆炸，问多少个化合物是不能装车的。思路：并查集的简单应用。实际上满足条件的时候是一个

本是古典何须时尚/ 2022年07月29日 10:53/ 0 赞/ 6 阅读

相关 poj1160

include<iostream> include<string.h> using namespace std; int a[301

逃离我推掉我的手/ 2022年06月18日 04:19/ 0 赞/ 136 阅读

相关 HDU 1160 FatMouse's Speed

原题目链接：[HDU1160][] -------------------- 分类 HDU 动态规划最长上升子序列 --------------------

电玩女神/ 2022年04月15日 02:25/ 0 赞/ 182 阅读

相关 1160. Network

1160. Network Time limit: 1.0 second Memory limit: 64 MB Andrew is working as system

àì夳堔傛蜴生んèń/ 2022年01月05日 15:37/ 0 赞/ 284 阅读

相关 uva 1160 - X-Plosives

/\ 题意：往仓库里放\\\，把关键引爆\\\的数对拿出并计数数学模型：输入数对，判断是否成环eg（1,2 2,3 3,4, 1,4）这个时候要计数。该题中让人

末蓝、/ 2021年12月16日 19:05/ 0 赞/ 174 阅读

相关 HDU-1160 FatMouse's Speed

链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1160][http_acm.hdu.edu.cn_showproblem.php_

╰半橙微兮°/ 2021年11月01日 14:46/ 0 赞/ 218 阅读

相关 hdu1160

[http://acm.hdu.edu.cn/showproblem.php?pid=1160][http_acm.hdu.edu.cn_showproblem.php_pid

￡神魔★判官ぃ/ 2021年10月19日 11:12/ 0 赞/ 231 阅读