网站建立初步教案,企业网站建设定制开发服务,吕梁网络推广,设计公司网站源码下载并查集
HDOJ-1232 畅通工程
题目#xff1a; 省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通#xff0c;输入现有城镇道路统计表#xff08;表中列出了每条道路直接连通的城镇#xff09;#xff0c;求最少还需要建设的道路数量。#xff08;城镇从1到…并查集
HDOJ-1232 畅通工程
题目 省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通输入现有城镇道路统计表表中列出了每条道路直接连通的城镇求最少还需要建设的道路数量。城镇从1到N编号
思路 将每组互相连通的城市视为一个不相交集合不与其他城市连通的城市也视为一个集合。 “使任何两个城镇间都可以实现交通”即将所有集合合并为一个集合。 题目每行输入定义该行的两个元素属于同一个集合将这两个元素所属集合合并。 本组输入处理完成之后满足set[i]i的城镇均为集长预处理 set[i]i,i1,2,…,n统计这样的城镇个数减去1即为最少需要建设的道路数量。
#includecstdio
int set[1005];
//set[i]①i,则i表示本集合并是集合对应树的根②j,j!i,则j是i的父节点
int find(int x)//x为待查找城镇的编号{while(set[x]!x) xset[x];return x;}//输出集长
int h[1005];//h[i]代表以i为集长的集树的深度
void merge(int m1,int m2){//合并两个城镇所在的集合m1find(m1);m2find(m2);if(m1!m2){//查找出两个城镇的集长不同则合并if(h[m1]h[m2]) {h[m1];set[m2]m1;}//如果深度相同集合m2转接至集合m1集合m1深度1else if(h[m1]h[m2]) set[m1]m2;//深度小的树合并到深度大的树else set[m2]m1;}
}
int main(){int n;while(scanf(%d,n)n){//n代表城镇数量int i,m,m1,m2;scanf(%d,m);//m代表已有道路数量for(i1;in;i) set[i]i;//各个城市初始化为一个独立的集合城市编号从1开始 for(i1;in;i) h[i]1;//各集树深度层数初始化为1while(m--){//依次读入各条道路scanf(%d%d,m1,m2);//m1,m2代表当前道路连通的两个城镇merge(m1,m2);}int count0;//count代表独立集合个数for(i1;in;i)if(set[i]i) count;count--;//最少建设道路数独立集合个数-1printf(%d\n,count);}return 0;
}HDOJ-1856 More is better
题目 在一个房间里有10000000个男孩他们的编号依次为12…, 10000000。在各个互相认识直接或间接的男孩之间组成了许多的朋友圈输入关系表表中每行中的两个男孩直接认识输出房间内最大的朋友圈的尺寸包含人数。
思路 每组互相认识的男孩属于同一个朋友圈将不与其他男孩认识的男孩也视为一个朋友圈。 题目的任务是确定朋友圈的最大尺寸。 题目每行输入定义该行的两个编号对应的男孩相互认识属于同一个朋友圈将这两个男孩所属朋友圈合并。 开辟数组记录朋友圈尺寸两个朋友圈合并时将它们的尺寸相加。 本组输入处理完成之后找出朋友圈的最大尺寸。 由于数据量较大要进行路径压缩。
#includecstdio
int set[10000005];
//set[i]①i,则i表示本集合并是集合对应树的根②j,j!i,则j是i的父节点
int find(int i){//i为待查找男孩的编号int ri;while(set[r]!r) rset[r];int t;while(i!r){//修改查找路径中所有节点tset[i];set[i]r;//使i指向rit;}return r;//输出圈长
}
int h[10000005];//h[i]代表以i为圈长的集树的深度
int size[10000005];//size[i]代表以i为圈长的朋友圈的尺寸
void merge(int m1,int m2){//合并两个男孩所在的朋友圈m1find(m1);m2find(m2);if(m1!m2){//查找出两个朋友圈的圈长不同则合并if(h[m1]h[m2]) {h[m1];set[m2]m1;size[m1]size[m2];}//朋友圈尺寸对应合并else if(h[m1]h[m2]) {set[m1]m2;size[m2]size[m1];}else {set[m2]m1;size[m1]size[m2];}}
}
int main(){int n;while(scanf(%d,n)!EOF){//n代表朋友对数量int i,m1,m2;for(i1;in;i) set[i]i;//各个男孩初始化为一个独立的朋友圈朋友圈编号从1开始 for(i1;in;i) {h[i]1;size[i]1;}//各朋友圈尺寸初始化为1for(i1;in;i){scanf(%d%d,m1,m2);//m1,m2代表当前认识的两个男孩merge(m1,m2);}int max1;//max代表朋友圈最大尺寸for(i1;in;i)if(size[i]max) maxsize[i];printf(%d\n,max);}return 0;
}最小生成树
给定无向图G(V,E)连接G中所有点且是E的子集的树称为G的生成树。所有路权值总和最小的生成树称为最小生成树。
求最小生成树的Kruskal算法步骤 一、把原始图的N个节点看成N个独立集合 二、所有边从短到长排序每次选取当前最短的边如果两端是否属于不同的集合进行合并 三、循环操作步骤二直到有N1条边 将每个村庄看作一个结点题目可归结为求连接所有结点的最小生成路的权值之和。
HDOJ-1233 还是畅通工程
题目 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现交通输入现有村庄分布统计表表中列出了任意两个村庄之间的距离计算需要建设的最小的公路总长度。乡村从1到N编号
#includecstdio
#includealgorithm
using namespace std;
struct road{int c1,c2;//c1,c2代表两个村庄编号int d;//d代表它们之间的距离}r[5000];
bool cmp(road x,road y){return x.dy.d;}//距离从小到大排序
int set[105];
int find(int x){while(set[x]!x) xset[x];return x;}
int h[105];
int merge(int m1,int m2){m1find(m1),m2find(m2);if(m1!m2){//查找出两个村庄的集长不同则合并if(h[m1]h[m2]) {h[m1];set[m2]m1;}else if(h[m1]h[m2]) set[m1]m2;else set[m2]m1;return 1;}return 0;
}
int main(){int n,i;while(scanf(%d,n)n){//n代表村庄数量int nmn*(n-1)/2;for(i0;inm;i)//依次读入各村庄间距离scanf(%d%d%d,r[i].c1,r[i].c2,r[i].d);sort(r,rnm,cmp); for(i1;in;i) set[i]i; for(i1;in;i) h[i]1;int sn0;//sn代表已经建造的道路数量int sd0;//sd代表已经建造的道路里程for(i0;inm;i){if(merge(r[i].c1,r[i].c2)1)//进行了合并{sn1;//新建一条道路sdr[i].d;}//两村庄间距离计入道路里程if(snn-1) break;}printf(%d\n,sd);}return 0;
}HDOJ-1879 继续畅通工程
题目 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现交通输入现有村庄道路统计表表中列出了任意两个乡村间修建道路的费用以及该道路是否已经修通的状态计算全省畅通需要的最低成本。乡村从1到N编号
【思路】本题坑点有些村庄已经连通建造这些已经连通的道路所需成本即权值应该记为0。
#includecstdio
#includealgorithm
using namespace std;
struct road{int c1,c2;//c1,c2代表两个村庄编号int d;//d代表此两村庄间道路的成本}r[5000];
bool cmp(road x,road y){return x.dy.d;}//距离从小到大排序
int set[105];
int find(int x){while(set[x]!x) xset[x];return x;}
int h[105];
int merge(int m1,int m2){m1find(m1),m2find(m2);if(m1!m2){//查找出两个村庄的集长不同则合并if(h[m1]h[m2]) {h[m1];set[m2]m1;}else if(h[m1]h[m2]) set[m1]m2;else set[m2]m1;return 1;}return 0;
}
int main(){int n,i;while(scanf(%d,n)n){//n代表村庄数量int nmn*(n-1)/2;int s;//s代表当前道路修建状态for(i0;inm;i)//依次读入各村庄间道路{scanf(%d%d%d%d,r[i].c1,r[i].c2,r[i].d,s);if(s1) r[i].d0;}//如果道路已修建未来成本为0sort(r,rnm,cmp); for(i1;in;i) set[i]i;for(i1;in;i) h[i]1;int sn0;//sn代表已经建造的道路数量int sd0;//sd代表累计花费的成本for(i0;inm;i){if(merge(r[i].c1,r[i].c2)1)//进行了合并{sn1;//新建一条道路sdr[i].d;}//计入成本if(snn-1) break;}printf(%d\n,sd);}return 0;
}HDOJ-1875 畅通工程再续
题目 有一个叫“百岛湖”的地方其中的居民生活在不同的小岛上。该景区“畅通工程”的目标是通过在符合条件的岛间建桥如果2个小岛之间的距离d满足10d1000则符合条件使全湖任何两个小岛间都可以实现陆上交通。输入各小岛的位置坐标桥的价格为 100元/米计算全湖畅通需要的最低成本。
思路 最小生成树。 相比1007变化之处需要自行计算各小岛间距离建桥对距离有要求。
#includecstdio
#includecmath
#includealgorithm
using namespace std;
struct dao{int num;//num代表小岛编号int x,y;//x,y代表小岛坐标}xd[105];
struct road{int num1,num2;//num1,num2代表两个小岛编号double d;//d代表两个小岛间距离}r[5000];
bool cmp(road x,road y){return x.dy.d;}
int set[105];
int find(int x){while(set[x]!x) xset[x];return x;}
int h[105];
int merge(int m1,int m2){m1find(m1),m2find(m2);if(m1!m2){if(h[m1]h[m2]) {h[m1];set[m2]m1;}else if(h[m1]h[m2]) set[m1]m2;else set[m2]m1;return 1;}return 0;
}
int main(){int t,c,i,j;scanf(%d,t);while(t--){scanf(%d,c);//c代表小岛数量for(i1;ic;i)//依次发放小岛编号读入坐标{xd[i].numi;scanf(%d%d,xd[i].x,xd[i].y);}double dis;//dis代表当前两个小岛间距离int cm0;//cm代表长度符合条件的道路数量for(i1;ic;i)for(ji1;jc;j){//依次计算小岛间距离dissqrt((xd[i].x-xd[j].x)*(xd[i].x-xd[j].x)(xd[i].y-xd[j].y)*(xd[i].y-xd[j].y));if(dis10dis1000) {cm;r[cm].num1i;r[cm].num2j;r[cm].ddis;}}if(cmc-1){sort(r1,r1cm,cmp); for(i1;ic;i) set[i]i;for(i1;ic;i) h[i]1;int sn0;//sn代表已经建造的道路数量double sd0;//sd代表累计建造的道路里程for(i1;icm;i){if(merge(r[i].num1,r[i].num2)1)//进行了合并{sn1;//新建一条道路sdr[i].d;}//计入里程if(snc-1) break;}printf(%.1lf\n,100.0*sd);}else printf(oh!\n);}return 0;
}POJ-2031 Building a Space Station
题目 空间站由多个半径不同的球形单元组成。反常的是两个单元可以彼此接触甚至可以有交叉重叠。 输入各单元的三维坐标和半径。试将所有单元用走廊连接起来走廊的端点在单元的表面上并使走廊总长度最短。两个接触或交叉重叠的单元视为已连接
思路 最小生成树 接触或交叉重叠判定球心距半径之和 两个单元直接相连的最短路径并不是球心距而是球心距-两者半径之和。
#includecstdio
#includecmath
#includealgorithm
using namespace std;
struct dao{int num;//num代表单元编号double x,y,z,r;//x,y,z代表单元坐标r为单元半径 }xd[105];
struct road{int num1,num2;//num1,num2代表两个单元编号double d;//d代表两个单元间距离}r[5000];
bool cmp(road x,road y){return x.dy.d;}
int set[105];
int find(int x){while(set[x]!x) xset[x];return x;}
int h[105];
int merge(int m1,int m2){m1find(m1),m2find(m2);if(m1!m2){if(h[m1]h[m2]) {h[m1];set[m2]m1;}else if(h[m1]h[m2]) set[m1]m2;else set[m2]m1;return 1;}return 0;
}
int main(){int c,i,j;while(scanf(%d,c)c){//c代表单元数量for(i1;ic;i)//依次发放单元编号读入坐标{xd[i].numi;scanf(%lf%lf%lf%lf,xd[i].x,xd[i].y,xd[i].z,xd[i].r);}double dis,dism;//dis代表当前两个单元球心间距离dism为最短距离 int cm0;//cm为尚未建设的道路数量 for(i1;ic;i) set[i]i;for(i1;ic;i) h[i]1;int sn0;//sn代表已经建造的道路数量for(i1;ic;i)for(ji1;jc;j){//依次计算单元间距离dissqrt(pow(xd[i].x-xd[j].x,2)pow(xd[i].y-xd[j].y,2)pow(xd[i].z-xd[j].z,2));dismdis-xd[i].r-xd[j].r;if(dism0fabs(dism)1e-6) {cm;r[cm].num1i;r[cm].num2j;r[cm].ddism;}else if(merge(i,j)) sn;//关键}double sd0;//sd代表累计建造的道路里程if(snc-1){sort(r1,r1cm,cmp); for(i1;icm;i){if(merge(r[i].num1,r[i].num2))//进行了合并{sn1;//新建一条道路sdr[i].d;}//计入里程if(snc-1) break;}}printf(%.3lf\n,sd);}return 0;
}【总结】两个相连的单元如果已经处于同一个集合则图的边数不应增加。
