电子商务毕业设计网站深圳整站全网推广

题目： 省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通，输入现有城镇道路统计表（表中列出了每条道路直接连通的城镇），求最少还需要建设的道路数量。（城镇从1到N编号）

思路：
将每组互相连通的城市视为一个不相交集合，不与其他城市连通的城市也视为一个集合。
“使任何两个城镇间都可以实现交通”即将所有集合合并为一个集合。
题目每行输入，定义该行的两个元素属于同一个集合，将这两个元素所属集合合并。
本组输入处理完成之后，满足set[i]==i的城镇均为集长（预处理： set[i]=i,i=1,2,…,n），统计这样的城镇个数，减去1，即为最少需要建设的道路数量。

#include<cstdio>
int set[1005];
//set[i]=①i,则i表示本集合，并是集合对应树的根；②j,j!=i,则j是i的父节点
int find(int x)//x为待查找城镇的编号{while(set[x]!=x) x=set[x];return x;}//输出集长
int h[1005];//h[i]代表以i为集长的集树的深度
void merge(int m1,int m2){//合并两个城镇所在的集合m1=find(m1);m2=find(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(i=1;i<=n;i++) set[i]=i;//各个城市初始化为一个独立的集合，城市编号从1开始		for(i=1;i<=n;i++) h[i]=1;//各集树深度（层数）初始化为1while(m--){//依次读入各条道路scanf("%d%d",&m1,&m2);//m1,m2代表当前道路连通的两个城镇merge(m1,m2);}int count=0;//count代表独立集合个数for(i=1;i<=n;i++)if(set[i]==i) count++;count--;//最少建设道路数=独立集合个数-1printf("%d\n",count);}return 0;
}

题目： 在一个房间里有10000000个男孩，他们的编号依次为1，2，…, 10000000。在各个互相认识（直接或间接）的男孩之间组成了许多的朋友圈，输入关系表，表中每行中的两个男孩直接认识，输出房间内最大的朋友圈的尺寸（包含人数）。

思路：
每组互相认识的男孩属于同一个朋友圈，将不与其他男孩认识的男孩也视为一个朋友圈。
题目的任务是确定朋友圈的最大尺寸。
题目每行输入，定义该行的两个编号对应的男孩相互认识，属于同一个朋友圈，将这两个男孩所属朋友圈合并。
开辟数组记录朋友圈尺寸，两个朋友圈合并时，将它们的尺寸相加。
本组输入处理完成之后，找出朋友圈的最大尺寸。
由于数据量较大，要进行路径压缩。

#include<cstdio>
int set[10000005];
//set[i]=①i,则i表示本集合，并是集合对应树的根；②j,j!=i,则j是i的父节点
int find(int i){//i为待查找男孩的编号int r=i;while(set[r]!=r) r=set[r];int t;while(i!=r){//修改查找路径中所有节点t=set[i];set[i]=r;//使i指向ri=t;}return r;//输出圈长
}
int h[10000005];//h[i]代表以i为圈长的集树的深度
int size[10000005];//size[i]代表以i为圈长的朋友圈的尺寸
void merge(int m1,int m2){//合并两个男孩所在的朋友圈m1=find(m1);m2=find(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(i=1;i<=n;i++) set[i]=i;//各个男孩初始化为一个独立的朋友圈，朋友圈编号从1开始		for(i=1;i<=n;i++) {h[i]=1;size[i]=1;}//各朋友圈尺寸初始化为1for(i=1;i<=n;i++){scanf("%d%d",&m1,&m2);//m1,m2代表当前认识的两个男孩merge(m1,m2);}int max=1;//max代表朋友圈最大尺寸for(i=1;i<=n;i++)if(size[i]>max) max=size[i];printf("%d\n",max);}return 0;
}

题目： 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现交通，输入现有村庄分布统计表（表中列出了任意两个村庄之间的距离），计算需要建设的最小的公路总长度。（乡村从1到N编号）

#include<cstdio>
#include<algorithm>
using namespace std;
struct road{int c1,c2;//c1,c2代表两个村庄编号int d;//d代表它们之间的距离}r[5000];
bool cmp(road x,road y){return x.d<y.d;}//距离从小到大排序
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(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 nm=n*(n-1)/2;for(i=0;i<nm;i++)//依次读入各村庄间距离scanf("%d%d%d",&r[i].c1,&r[i].c2,&r[i].d);sort(r,r+nm,cmp);		for(i=1;i<=n;i++) set[i]=i;		for(i=1;i<=n;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量int sd=0;//sd代表已经建造的道路里程for(i=0;i<nm;i++){if(merge(r[i].c1,r[i].c2)==1)//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//两村庄间距离计入道路里程if(sn==n-1) break;}printf("%d\n",sd);}return 0;
}

题目： 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现交通，输入现有村庄道路统计表（表中列出了任意两个乡村间修建道路的费用，以及该道路是否已经修通的状态），计算全省畅通需要的最低成本。（乡村从1到N编号）

【思路】本题坑点：有些村庄已经连通，建造这些已经连通的道路所需成本（即权值）应该记为0。

#include<cstdio>
#include<algorithm>
using namespace std;
struct road{int c1,c2;//c1,c2代表两个村庄编号int d;//d代表此两村庄间道路的成本}r[5000];
bool cmp(road x,road y){return x.d<y.d;}//距离从小到大排序
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(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 nm=n*(n-1)/2;int s;//s代表当前道路修建状态for(i=0;i<nm;i++)//依次读入各村庄间道路{scanf("%d%d%d%d",&r[i].c1,&r[i].c2,&r[i].d,&s);if(s==1) r[i].d=0;}//如果道路已修建，未来成本为0sort(r,r+nm,cmp);		for(i=1;i<=n;i++) set[i]=i;for(i=1;i<=n;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量int sd=0;//sd代表累计花费的成本for(i=0;i<nm;i++){if(merge(r[i].c1,r[i].c2)==1)//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//计入成本if(sn==n-1) break;}printf("%d\n",sd);}return 0;
}

题目： 有一个叫“百岛湖”的地方，其中的居民生活在不同的小岛上。该景区“畅通工程”的目标是通过在符合条件的岛间建桥（如果2个小岛之间的距离d满足10<=d<=1000，则符合条件）使全湖任何两个小岛间都可以实现陆上交通。输入各小岛的位置坐标，桥的价格为 100元/米，计算全湖畅通需要的最低成本。

思路：
最小生成树。
相比1007变化之处：需要自行计算各小岛间距离；建桥对距离有要求。

#include<cstdio>
#include<cmath>
#include<algorithm>
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.d<y.d;}
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(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(i=1;i<=c;i++)//依次发放小岛编号，读入坐标{xd[i].num=i;scanf("%d%d",&xd[i].x,&xd[i].y);}double dis;//dis代表当前两个小岛间距离int cm=0;//cm代表长度符合条件的道路数量for(i=1;i<=c;i++)for(j=i+1;j<=c;j++){//依次计算小岛间距离dis=sqrt((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(dis>=10&&dis<=1000) {cm++;r[cm].num1=i;r[cm].num2=j;r[cm].d=dis;}}if(cm>=c-1){sort(r+1,r+1+cm,cmp);		for(i=1;i<=c;i++) set[i]=i;for(i=1;i<=c;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量double sd=0;//sd代表累计建造的道路里程for(i=1;i<=cm;i++){if(merge(r[i].num1,r[i].num2)==1)//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//计入里程if(sn==c-1) break;}printf("%.1lf\n",100.0*sd);}else printf("oh!\n");}return 0;
}

题目：
空间站由多个半径不同的球形单元组成。反常的是，两个单元可以彼此接触，甚至可以有交叉重叠。
输入各单元的三维坐标和半径。试将所有单元用走廊连接起来（走廊的端点在单元的表面上），并使走廊总长度最短。（两个接触或交叉重叠的单元视为已连接）

思路：
最小生成树
接触或交叉重叠判定：球心距<=半径之和
两个单元直接相连的最短路径并不是球心距，而是球心距-两者半径之和。

#include<cstdio>
#include<cmath>
#include<algorithm>
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.d<y.d;}
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(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(i=1;i<=c;i++)//依次发放单元编号，读入坐标{xd[i].num=i;scanf("%lf%lf%lf%lf",&xd[i].x,&xd[i].y,&xd[i].z,&xd[i].r);}double dis,dism;//dis代表当前两个单元球心间距离，dism为最短距离 int cm=0;//cm为尚未建设的道路数量		for(i=1;i<=c;i++) set[i]=i;for(i=1;i<=c;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量for(i=1;i<=c;i++)for(j=i+1;j<=c;j++){//依次计算单元间距离dis=sqrt(pow(xd[i].x-xd[j].x,2)+pow(xd[i].y-xd[j].y,2)+pow(xd[i].z-xd[j].z,2));dism=dis-xd[i].r-xd[j].r;if(dism>0&&fabs(dism)>1e-6) {cm++;r[cm].num1=i;r[cm].num2=j;r[cm].d=dism;}else if(merge(i,j)) sn++;//关键}double sd=0;//sd代表累计建造的道路里程if(sn<c-1){sort(r+1,r+1+cm,cmp);		for(i=1;i<=cm;i++){if(merge(r[i].num1,r[i].num2))//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//计入里程if(sn==c-1) break;}}printf("%.3lf\n",sd);}return 0;
}

【总结】两个相连的单元，如果已经处于同一个集合，则图的边数不应增加。