UVa/LA|UVa10048 - Audiophobia（floyed|最小生成树） UVa

题目链接
简介：
要求两点之间最大路径权值最小，输出这个最大路径
分析：
书上给了一种很简单的做法：floyed

G[i][j]=min(G[i][j],max(G[i][k],G[k][j]));

这样做为什么对呢？
因为无论是floyed和dijkstra，都是基于这样一个事实：
对于任何一条至少包含两条边的路径i—>j，一定存在一个k，使得i—>j的总长度等于i—>k和k—>j的路径和
对于不同的点k，i—>k和k—>j的长度之和可能不同，但是最后还需要取一个min

//这里写代码片 #include #include #includeusing namespace std; const int INF=0x33333333; int f[103][103]; int G[103][103]; int n,m,Q; void floyed() { int i,j,k; for (k=1; k<=n; k++) for (i=1; i<=n; i++) if (i!=k) for (j=1; j<=n; j++) { G[i][j]=min(G[i][j],max(G[i][k],G[k][j])); } }int main() { int cnt=0; while (scanf("%d%d%d",&n,&m,&Q)!=EOF&&n) { if (cnt++) printf("\n"); printf("Case #%d\n",cnt); memset(G,0x33,sizeof(G)); for (int i=1; i<=m; i++) { int u,w,z; scanf("%d%d%d",&u,&w,&z); G[u][w]=G[w][u]=z; } floyed(); for (int i=1; i<=Q; i++) { int u,w; scanf("%d%d",&u,&w); if (G[u][w]==INF) printf("no path\n"); else printf("%d\n",G[u][w]); } } return 0; }

【UVa/LA|UVa10048 - Audiophobia（floyed|最小生成树）】但是我一开始想到的不是这个做法，而是最小生成树
结果证明这也是对的
唯一需要注意的就是图不一定联通，所以每个连通块都要dfs一遍
这样的复杂度应该是O(n^2)，比floyed好，但是代码较长，需要注意细节

//这里写代码片 #include #include #include #includeusing namespace std; const int INF=0x33333333; int f[103][103]; struct node{ int x,y,v,nxt; bool operator < (const node &a) const { return v210],e[1003]; int n,m,Q,st[103],tot,fa[103]; int p[103]; void unionn(int f1,int f2){fa[f1]=f2; } int find(int x) { if (fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; }void add(int u,int w,int v) { tot++; way[tot].x=u; way[tot].y=w; way[tot].v=v; way[tot].nxt=st[u]; st[u]=tot; tot++; way[tot].x=w; way[tot].y=u; way[tot].v=v; way[tot].nxt=st[w]; st[w]=tot; }void Kruskal() { sort(e+1,e+1+m); for (int i=1; i<=n; i++) fa[i]=i; for (int i=1; i<=m; i++) { int f1=find(e[i].x); int f2=find(e[i].y); if (f1!=f2) { unionn(f1,f2); add(e[i].x,e[i].y,e[i].v); } } }void dfs(int now,int ff,int z,int bz) { for (int i=1; i<=n; i++) if (p[i]==bz) { f[i][now]=max(f[i][ff],z); f[now][i]=f[i][now]; } p[now]=bz; //在这里改标记 for (int i=st[now]; i; i=way[i].nxt) if (way[i].y!=ff) { f[now][way[i].y]=f[way[i].y][now]=way[i].v; // dfs(way[i].y,now,way[i].v,bz); } }int main() { int cnt=0; while (scanf("%d%d%d",&n,&m,&Q)!=EOF&&n) { if (cnt++) printf("\n"); printf("Case #%d\n",cnt); memset(st,0,sizeof(st)); tot=0; for (int i=1; i<=m; i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v); Kruskal(); memset(p,0,sizeof(p)); memset(f,128,sizeof(f)); for (int i=1; i<=n; i++) if (p[i]==0) dfs(i,0,0,i); for (int i=1; i<=Q; i++) { int u,w; scanf("%d%d",&u,&w); if (f[u][w]<0) printf("no path\n"); else printf("%d\n",f[u][w]); } } return 0; }