【HDU神他么畅通工程系列】--TBC

2019-11-06 07:54:00

字体：大中小

来源：转载

供稿：网友

占神坑 HDU 1232【并查集】想法：并查集水题。把每个城镇放到一个集合里，想要连通两个城镇，只要连通集合里的任意一个点就行。两个城镇连通了即f[i]==i时（两个点是一个祖先了），道路数要-1啊。

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int f[1005];int find(int x){ if(f[x]==x) return x; else { f[x]=find(f[x]); return f[x]; }}void join(int u,int v){ int t1,t2; t1=find(u); t2=find(v); if(t1!=t2) { f[t2]=t1; }}int main(){ int n,m,a,b,i,cou; while(scanf("%d %d",&n,&m)&&n)// {//这种判断不为0的方法最后输入0按回车后不会直接按任意键结束，所以以为错到怀疑世界，结果某猪说的对，按crtl+z加回车两次就可以了=3= cou=0; for(i=1; i<=n; i++) { f[i]=i; } for(i=1; i<=m; i++) { scanf("%d %d",&a,&b); join(a,b); } for(i=1; i<=n; i++) { if(f[i]==i) cou++; } PRintf("%d/n",cou-1); } return 0;}

HDU 1233【最下生成树】

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int f[105];struct edge{ int u,v,w;};//存点edge e[5000];int cmp(edge a,edge b){ return a.w<b.w;//给边排序}int find(int x)//寻找这个点在哪个集合里{ if(f[x]==x) return x; else {//wa了十多遍到怀疑人生 f[x]=find(f[x]);//发现是把这个赋值号写成了等于号（手动再见） return f[x]; }}int join(int a,int b)//把两个点放到一个集合里代表连通了{ int t1,t2; t1=find(a); t2=find(b); if(t1!=t2) { f[t2]=t1; return 1; } return 0;}int main(){ int n,i,a,b,c; int sum,cou; while(scanf("%d",&n),n) { int m=(n*(n-1))/2; sum=0; cou=0;//次数要是n-1 memset(e,0,sizeof(e)); memset(f,0,sizeof(f)); for(i=1;i<=m;i++)//m行 { scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);//每一行的a,b,c } sort(e+1,e+m+1,cmp);//从第一个点到最后一个点的任意一个点之间从小到大排序 for(i=1;i<=n;i++) { f[i]=i; } for(i=1;i<=m;i++) { if(join(e[i].u,e[i].v)) { cou++; sum+=e[i].w;//如果两个点连通了，累积他们的长度 } if(cou==n-1)//n个点，连n-1条边就好 break; } printf("%d/n",sum); } return 0;}

HDU 1863 【最小生成树】想法：最小生成树水题，只是把距离换成了成本。

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int f[105];struct edge{ int u,v,w;};edge e[5500];int cmp(edge a,edge b){ return a.w<b.w;}int find(int x){ if(f[x]==x) return x; else { f[x]=find(f[x]); return f[x]; }}int join(int u,int v){ int d1=find(u); int d2=find(v); if(d1!=d2) { f[d2]=d1; return 1; } return 0;}int main(){ int flag=0; int n,m,u,v,w,i; int sum,cou; while(scanf("%d %d",&n,&m),n) { memset(f,0,sizeof(f)); memset(e,0,sizeof(e)); cou=0; sum=0; for(i=1;i<=n;i++) { scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); } sort(e+1,e+n+1,cmp); for(i=1;i<=m;i++) { f[i]=i; } for(i=1;i<=n;i++) { if(join(e[i].u,e[i].v)) { sum+=e[i].w; cou++; } } if(cou==m-1)/应该修的路肯定是要与村庄m比较啊 cout<<sum<<endl; else cout<<"?"<<endl; } return 0;}

HDU 1874 HDU 1875 HDU 1879

上一篇：Round Numbers POJ - 3252 （数位DP）题解

下一篇：qt5.1.1 + opencv2.4.10 + cmake3.7.2环境搭建