为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
URAL/1004
来自NOCOW
< URAL
#include <iostream> using namespace std; const int maxn=122, maxint=50022; int d[maxn], a[maxn][maxn], list[maxn], que[maxn], fa[maxn], ans, top, n, m; bool inque[maxn], b[maxn][maxn]; int nex(int x){return ++x>=maxn?0:x;} void print(){ if(top==0)printf("No solution.\n"); else{ printf("%d", list[top]); for(int i=top-1;i>0;--i)printf(" %d", list[i]); printf("\n"); } } void done(int x, int y){ int s=0, t=1, h; b[x][y]=false, b[y][x]=false; for(int i=1;i<=n;++i){d[i]=maxint, fa[i]=i, inque[i]=false;} d[x]=0, que[1]=x, inque[x]=true; while(nex(t)!=s){ s=nex(s), h=que[s], inque[h]=false; for(int i=1;i<=n;++i) if(b[h][i] && d[i]>d[h]+a[h][i]){ d[i]=d[h]+a[h][i], fa[i]=h; if(!inque[i]){t=nex(t), que[t]=i, inque[i]=true;} } } if(ans>d[y]+a[x][y]){ ans=d[y]+a[x][y], top=0; while(y!=fa[y]){list[++top]=y, y=fa[y];} list[++top]=y; } b[x][y]=true, b[y][x]=true; } int main(){ scanf("%d", &n); while(n!=-1){ scanf("%d", &m); top=0, ans=maxint; memset(b, false, sizeof(b)); int x, y, z; for(int i=0;i<m;++i){ scanf("%d%d%d", &x, &y, &z); if(!b[x][y]){a[x][y]=z, a[y][x]=z, b[x][y]=true, b[y][x]=true;} else if(a[x][y]>z){a[x][y]=z, a[y][x]=z;} } for(int i=1;i<n;++i)for(int j=i+1;j<=n;++j)if(b[i][j])done(i, j); print(); scanf("%d", &n); } return 0; } //by sky
//深搜不解释 #include<stdio.h> #include<string.h> int b[110][110],n,m,c[110],ans[110],jilu2; bool bo[110]; void dfs(int k,int x,int jilu,int len) { int i; if (jilu>=jilu2)return; if (k==x&&len!=1){ ans[0]=len;jilu2=jilu; for (i=1;i<=len;i++)ans[i]=c[i]; } else { for (i=1;i<=n;i++) { if (i!=x&&bo[i]) { if (i==k&&len==2)continue; len++;c[len]=i;bo[i]=false;jilu+=b[x][i]; dfs(k,i,jilu,len); jilu-=b[x][i];c[len]=0;len--;bo[i]=true; } } } } int main() { int i,x,y,d,k; while (scanf("%d",&n),n>-1) { scanf("%d",&m); memset(b,63,sizeof(b)); memset(bo,true,sizeof(bo)); for (i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&d); if (d<b[x][y])b[x][y]=b[y][x]=d; } ans[0]=0;jilu2=999999999; for (i=1;i<=n;i++){ c[1]=i;;dfs(i,i,0,1); } if (ans[0]==0)printf("No solution.\n"); else { for (i=1;i<ans[0]-1;i++)printf("%d ",ans[i]); printf("%d\n",ans[ans[0]-1]); } } } //by zjw
Floyd求最小环
var dis,mid,g:array[1..100,1..100] of longint; x,y,c,z,i,n,m,best,k:longint; ans:array[1..100] of longint; procedure get(x,y:longint); begin if mid[x,y]=-1 then exit; get(x,mid[x,y]); inc(c); ans[c]:=mid[x,y]; get(mid[x,y],y); end; begin while true do begin best:=100001; fillchar(dis,sizeof(dis),26); fillchar(mid,sizeof(mid),255); c:=0; read(n);if n=-1 then break; readln(m); for i:=1 to m do begin readln(x,y,z); if z<dis[x,y] then begin dis[x,y]:=z; dis[y,x]:=z; end; end; g:=dis; for k:=1 to n do begin for x:=1 to k do if x<>k then for y:=1 to k do if x<>y then if dis[x,k]+dis[k,y]+g[x,y]<best then begin best:=dis[x,k]+dis[k,y]+g[x,y]; c:=1; ans[c]:=k; inc(c); ans[c]:=x; get(x,y); inc(c); ans[c]:=y; end; // for x:=1 to n-1 do for y:=x+1 to n do if g[x,k]+g[k,y]<g[x,y] then begin g[x,y]:=g[x,k]+g[k,y]; g[y,x]:=g[x,y]; mid[x,y]:=k; mid[y,x]:=k; end; end; if c=0 then writeln('No solution.') else begin for i:=1 to c-1 do write(ans[i],' '); writeln(ans[c]); end; end;//while end. from 3144046cjc
贴个cpp的……
#include <cstdio> #include <cstring> const int oo=1000000000,maxn=111; int n,m,g[maxn][maxn],c[maxn][maxn],path[maxn][maxn],f[maxn][maxn],p,q,l,ans; void Dfs(int l,int r){ int t=path[l][r]; if (path[l][t]) Dfs(l,t); printf("%d ",t); if (path[t][r]) Dfs(t,r); } int main(){ freopen("s.in","r",stdin); freopen("s.out","w",stdout); scanf("%d",&n); while (n!=-1){ scanf("%d",&m); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) g[i][j]=oo; memset(c,0,sizeof(c)); memset(path,0,sizeof(path)); ans=oo; int x,y,z; for (int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); if (g[x][y]==-1 || z<g[x][y]) g[x][y]=g[y][x]=z; } memcpy(f,g,sizeof f); for (int k=1;k<=n;k++){ for (int i=1;i<=n;i++) if (g[k][i]!=oo) for (int j=i+1;j<=n;j++) if (g[j][k]!=oo) if (f[i][j]+g[k][i]+g[k][j]<ans){ ans=f[i][j]+g[k][i]+g[k][j]; p=i,q=j,l=k; memcpy(path,c,sizeof path); } for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (f[i][k]+f[k][j]<f[i][j]){ f[j][i]=f[i][j]=f[i][k]+f[k][j]; c[i][j]=c[j][i]=k; } } if (ans==oo) printf("No solution.\n"); else{ printf("%d %d ",l,p); if (path[p][q]) Dfs(p,q); printf("%d\n",q); } scanf("%d",&n); } return 0; }
/*gaoshangbo*/ //floyd 求最小环 #include <iostream> #include <stdio.h> using namespace std; #define M 10000000 int dist[105][105], data[105][105]; int n, t, path[105], f[105][105], mins; void extend_floyd() { int i, j, k, tmp, st; mins = M; for(k = 1; k <= n; k ++) { for(i = 1; i < k; i ++) { for(j = i+1; j < k; j ++) { tmp = data[i][j] + dist[j][k] + dist[k][i]; if(tmp < mins) { mins = tmp; st = j; t = 0; while(st != i) { path[t++] = st; st = f[i][st]; } path[t++] = i; path[t++] = k; } } } for(i = 1; i <= n; i ++) { for(j = 1; j <= n; j ++) { tmp = data[i][k] + data[k][j]; if(tmp < data[i][j]) { data[i][j] = tmp; f[i][j] = f[k][j]; } } } } } int main() { int m, i, j, x, y, d; while(scanf("%d", &n) && n != -1) { scanf("%d", &m); for(i = 1; i <= n; i ++) { for(j = 1; j <= n; j ++) { dist[i][j] = data[i][j] = M; f[i][j] = i; } } for(i = 1; i <= m; i ++) { scanf("%d%d%d", &x, &y, &d); dist[x][y] = dist[y][x] = data[x][y] = data[y][x] = min(data[y][x], d); } extend_floyd(); if(mins == M) printf("No solution.\n"); else { printf("%d", path[0]); for(i = 1; i < t; i ++) printf(" %d", path[i]); printf("\n"); } } return 0; }
//power721 #include<cstdio> #include<cstring> #define inf 99999999 int n,m,adj[105][105],dis[105][105],cnt,a[105],pre[105][105]; void dfs(int s,int e) { if(pre[s][e]) { dfs(s,pre[s][e]); dfs(pre[s][e],e); } else a[cnt++]=e; } int main() { while(scanf("%d",&n),n!=-1) { int i,j,k,ans=inf; for(i=1;i<=n;i++) for(j=1;j<=n;j++) adj[i][j]=inf; memset(pre,0,sizeof(pre)); scanf("%d",&m); while(m--) { scanf("%d%d%d",&i,&j,&k); if(k<adj[i][j]) adj[i][j]=adj[j][i]=k; } memcpy(dis,adj,sizeof(adj)); for(k=1;k<=n;k++) { for(i=1;i<k;i++) for(j=i+1;j<k;j++) if(ans>dis[i][j]+adj[i][k]+adj[k][j]) { cnt=0; a[cnt++]=i; dfs(i,j); a[cnt++]=k; ans=dis[i][j]+adj[i][k]+adj[k][j]; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j&&dis[i][j]>dis[i][k]+dis[k][j]) { dis[i][j]=dis[i][k]+dis[k][j]; pre[i][j]=k; } } if(ans<inf) { for(i=0;i<cnt;i++) printf("%d ",a[i]); puts(""); } else puts("No solution."); } }
#include<stdio.h> #include<stdlib.h> #include<string.h> int map[110][110]; int p[110],anss[110]; bool bo[110]; int n,m,ans,kk,lenn; bool bk; int min(int a,int b) { if (a<b) return a;else return b; } void dfs(int k,int lu,int len) { if (lu>ans) return; else if (len>2 && bo[kk]==false) { ans=lu; lenn=len; bk=true; for (int j=1;j<=n;j++) anss[j]=p[j]; } else if (bo[kk]) { for (int i=1;i<=n;i++) { if (k!=i && bo[i]) { p[len+1]=k; bo[i]=false; dfs(i,lu+map[k][i],len+1); p[len+1]=0; bo[i]=true; } } } } int main() { while (scanf("%d",&n)!=EOF && n!=-1) { memset(map,63,sizeof(map)); scanf("%d",&m); for (int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if (c<map[a][b]) { map[a][b]=c; map[b][a]=c; } } /*for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) map[i][j]=min(map[i][j],map[i][k]+map[k][j]);*/ ans=999999999; memset(anss,0,sizeof(anss)); memset(bo,true,sizeof(bo)); bk=false; for (kk=1;kk<=n;kk++) { memset(p,255,sizeof(p)); dfs(kk,0,0); } if (bk==false) printf("No solution.\n"); else { for (int i=1;i<=lenn-1;i++) printf("%d ",anss[i]); printf("%d\n",anss[lenn]); } } }
//by Exia
