哈密尔顿环

xiaoxiao2021-02-28 103

#include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<cmath> #include<iomanip> #include<queue> #include<cstring> using namespace std; #define maxn 101 bool visit[maxn],v1[maxn]; int ans[maxn],num[maxn],g[maxn][maxn]; int x,n,m,length; void print() { for(int i=1;i<=length-1;i++) { cout<<ans[i]<<' '; } cout<<ans[length]<<endl; } void dfs(int last,int i) { visit[i]=true; v1[i]=true; ans[++length]=i; for(int j=1;j<=num[i];j++) { if(g[i][j]==x&&g[i][j]!=last) { ans[++length]=g[i][j]; print(); length--; break; } if(!visit[g[i][j]]) dfs(i,g[i][j]); } length--; visit[i]=false; } int main() { memset(visit,false,sizeof(visit)); memset(v1,false,sizeof(v1)); memset(num,0,sizeof(num)); memset(ans,0,sizeof(ans)); memset(g,0,sizeof(g)); cin>>n>>m; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; g[x][++num[x]]=y; g[y][++num[y]]=x; } for(x=1;x<=n;x++) { if(!v1[x]) { length=0; dfs(0,x); } } return 0; }

P474 牛的旅行

#include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<cmath> #include<iomanip> #include<queue> #include<cstring> using namespace std; #define maxn 151 #define inf 1e12 int x[maxn],y[maxn]; double a[maxn][maxn],m[maxn]; double dis(int i,int j) { return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } int main() { int i,j,k,n; char c; double minn,max1; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&x[i],&y[i]); m[i]=0; } memset(a,0,sizeof(a)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cin>>c; if(c=='0') a[i][j]=inf; else a[i][j]=dis(i,j); } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if((k!=i)&&(i!=j)&&(k!=j)) { if(a[i][k]<inf-1&&a[k][j]<inf-1) { if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j]; } } } max1=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(a[i][j]<inf-1&&m[i]<a[i][j]) m[i]=a[i][j]; } if(m[i]>max1) max1=m[i]; } minn=1e20; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i!=j&&a[i][j]>inf-1) { double temp=dis(i,j); if(minn>m[i]+m[j]+temp) minn=m[i]+m[j]+temp; } } if(max1>minn) minn=max1; printf("%.6lf\n",minn); return 0; }

转载请注明原文地址: https://www.6miu.com/read-32619.html

技术

最新回复(0)