基于百度地图的网站开发,网上定制西装,手机网站模板开发工具,网站内链怎么优化HDU1213
http://acm.hdu.edu.cn/showproblem.php?pid1213
问题描述
今天是伊格纳修斯的生日。他邀请了很多朋友。现在是晚餐时间。伊格纳修斯想知道他至少需要多少桌子。你必须注意到并非所有的朋友都互相认识#xff0c;而且所有的朋友都不想和陌生人呆在一起。 这个问题…HDU1213
http://acm.hdu.edu.cn/showproblem.php?pid1213
问题描述
今天是伊格纳修斯的生日。他邀请了很多朋友。现在是晚餐时间。伊格纳修斯想知道他至少需要多少桌子。你必须注意到并非所有的朋友都互相认识而且所有的朋友都不想和陌生人呆在一起。 这个问题的一个重要规则是如果我告诉你A知道BB知道C那意味着ABC彼此了解所以他们可以留在一个表中。 例如如果我告诉你A知道BB知道CD知道E所以ABC可以留在一个表中DE必须留在另一个表中。所以Ignatius至少需要2张桌子。
输入
输入以整数T1 T 25开始表示测试用例的数量。然后是T测试案例。每个测试用例以两个整数N和M开始1 NM 1000。N表示朋友的数量朋友从1到N标记。然后M行跟随。每一行由两个整数A和BA B组成这意味着朋友A和朋友B彼此了解。两个案例之间会有一个空白行。 对于每个测试用例只输出Ignatius至少需要多少个表。不要打印任何空白。
样本输入
2
5 3
1 2
2 3
4 5 5 1
2 5
样本输出
2
4
并查集基础题
#includecstdio
#includeiostream
using namespace std;
int fa[1005];
int n,m;
void init()//初始化
{for(int i0;i1005;i)fa[i]i;
}
int find(int x)//寻根
{if(fa[x]!x)fa[x]find(fa[x]);return fa[x];
}
void union(int x,int y)//判断、合并
{int afind(x),bfind(y);if(a!b)fa[b]a;
}
int main()
{int t;scanf(%d,t);while(t--){int a,b,cnt0;scanf(%d%d,n,m);init();for(int i1;im;i)//合并{scanf(%d%d,a,b);union(a,b);}for(int i1;in;i)//统计{find(i);if(find(i)i)cnt;}printf(%d\n,cnt);}return 0;
}POJ1611
http://poj.org/problem?id1611
描述
严重急性呼吸系统综合症SARS是一种病因不明的非典型肺炎在2003年3月中旬被认为是一种全球性威胁。为了尽量减少对他人的传播最好的策略是将嫌疑人与其他嫌疑人分开。 在Not-Spreading-Your-Sickness UniversityNSYSU有许多学生团体。同一组中的学生经常互相交流学生可以加入几个小组。为了防止可能的SARS传播NSYSU收集所有学生组的成员列表并在其标准操作程序SOP中制定以下规则。 一旦组中的成员是嫌疑人该组中的所有成员都是嫌疑人。 然而他们发现当学生被认定为嫌疑人时识别所有嫌疑人并不容易。你的工作是编写一个找到所有嫌疑人的程序。
输入
输入文件包含几种情况。每个测试用例以一行中的两个整数n和m开始其中n是学生数m是组的数量。您可以假设0 n 30000且0 m 500.每个学生都使用0到n-1之间的唯一整数进行编号并且最初学生0在所有情况下都被识别为嫌疑人。该行后面是组的m个成员列表每组一行。每行以整数k开头表示组中的成员数。在成员数量之后有k个整数代表该组中的学生。一行中的所有整数由至少一个空格分隔。
n 0且m 0的情况表示输入结束无需处理。 对于每种情况输出一行中的嫌疑人数量。
样本输入
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
样本输出
4
1
1 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#include string
using namespace std;
int a[30001],pre[30001];
int find(int x)//寻根
{if(pre[x]x)return x;elsereturn pre[x]find(pre[x]);
}
void union(int x, int y)//合并
{int fx find(x), fy find(y);if (fx ! fy)pre[fy] fx;
}int main()
{int n,m;while (scanf(%d%d, n, m) ! EOF (n || m)){int sum 0;for (int i 0; i n; i)//初始化pre[i] i;for (int i 0; i m; i){int k;scanf(%d, k);if (k 1){scanf(%d, a[0]);for (int j 1; j k; j){scanf(%d, a[j]);//接收union(a[0], a[j]);//和0号一组}}}for (int i 0; i n; i)//统计if (find(i) pre[0])sum;printf(%d\n, sum);}return 0;
}POJ2236
http://poj.org/problem?id2236
描述
地震发生在东南亚。ACM亚洲合作医疗团队已经与膝上电脑建立了无线网络但是一次意外的余震袭击网络中的所有计算机都被打破了。计算机一个接一个地修复网络逐渐开始工作。由于硬件限制每台计算机只能直接与距离它不远的计算机进行通信。但是每台计算机都可以被视为两台计算机之间通信的中介也就是说如果计算机A和计算机B可以直接通信或者计算机C可以与A和A进行通信则计算机A和计算机B可以进行通信。 B. 在修复网络的过程中工作人员可以随时进行两种操作修复计算机或测试两台计算机是否可以通信。你的工作是回答所有的测试操作。
输入
第一行包含两个整数N和d1 N 1001,0 d 20000。这里N是计算机的数量编号从1到ND是两台计算机可以直接通信的最大距离。在接下来的N行中每行包含两个整数xiyi0 xiyi 10000这是N台计算机的坐标。从第N 1行到输入结束有一些操作这些操作是一个接一个地执行的。每行包含以下两种格式之一的操作 1。“O p”1 p N表示修复计算机p。 2.“S p q”1 pq N这意味着测试计算机p和q是否可以通信。 输入不会超过300000行。
产量
对于每个测试操作如果两台计算机可以通信则打印“SUCCESS”否则打印“FAIL”。
样本输入
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
样本输出
FAIL
SUCCESS 思路对每次修好的电脑对其它已经修好的电脑遍历如果距离小于等于最大通信距离就将他们合并。
注意 1、坐标之后给出的计算机编号都是n1的。例如O 3他实际上修理的是编号为2的计算机因为计算机是从0开始编号的。 2、比较距离的时候注意要用浮点数比较否则会WA。 3、FAIL不要写成FALL。 4、字符串输入的时候注意处理好回车空格等情况。 5、注意N的范围1 N 1001最大是1001不是1000。是个小坑数组开小了可能会错哦。 #include iostream
#include stdio.h
#include cmath
using namespace std;#define MAXN 1010int dx[MAXN],dy[MAXN]; //坐标
int par[MAXN]; //x的父节点
int repair[MAXN] {0};
int n;void Init()//初始化
{int i;for(i0;in;i)par[i] i;
}int Find(int x)//寻根
{if(par[x]!x)par[x] Find(par[x]);return par[x];
}void Union(int x,int y)//合并
{par[Find(x)] Find(y);
}int Abs(int n)//绝对值
{return n0?n:-n;
}double Dis(int a,int b)//坐标
{return sqrt( double(dx[a]-dx[b])*(dx[a]-dx[b]) (dy[a]-dy[b])*(dy[a]-dy[b]) );
}int main()
{int d,i;//初始化scanf(%d%d,n,d);Init();//输入坐标for(i0;in;i){scanf(%d%d,dx[i],dy[i]);}//操作char cmd[2];int p,q,len0;while(scanf(%s,cmd)!EOF){switch(cmd[0]){case O:scanf(%d,p);p--;repair[len] p;for(i0;ilen-1;i) //遍历所有修过的计算机看能否联通if( repair[i]!p Dis(repair[i],p)double(d) )Union(repair[i],p);break;case S:scanf(%d%d,p,q);p--,q--;if(Find(p)Find(q)) //判断printf(SUCCESS\n);else printf(FAIL\n);default:break;}}return 0;
}
