题解 UVA10048 【Audiophobia】

2018-08-17 14:46:17


考虑构造原图的最小生成树。

显然,对于所有从 $A$ 到 $B$ 的路径,走最小生成树上的路径最长边是最短的。

这个很容易用反证法证明出来。

那么我们先构造出最小生成树,然后Dfs找点即可。

细节见代码:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge {
    int u,v,w;
    bool operator <(const Edge& rhs) const {
        return w<rhs.w;
    }
};
Edge e[2010];
int n,m,q;

int root[110];
inline int find(int x) {
    if (root[x]!=x) root[x]=find(root[x]);
    return root[x];
}
inline void merge(int a,int b) {
    a=find(a),b=find(b);
    if (a!=b) root[a]=b;
}

struct newEdge { int v,w,nxt; };
newEdge E[2010];
int head[110],cnt=0;

inline void addEdge(int u,int v,int w) {
    E[++cnt].v=v; E[cnt].w=w;
    E[cnt].nxt=head[u]; head[u]=cnt;
}

inline void Kruskal() {
    sort(e+1,e+m+1);
    for (re int i=1;i<=n;i++) root[i]=i;
    for (re int i=1;i<=m;i++) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (find(u)!=find(v)) {
            merge(u,v);
            addEdge(u,v,w);
            addEdge(v,u,w);
        }
    }
}

inline int Dfs(int u,int to,int fa,int MAX) {
    for (re int i=head[u];i;i=E[i].nxt) {
        int v=E[i].v,w=E[i].w;
        if (v==to) return max(MAX,w);
        else if (v!=fa) {
            int k=Dfs(v,to,u,max(MAX,w));
            if (k!=-1) return k;
        }
    }
    return -1;
}

int main() {
    int T=0;
    while (scanf("%d%d%d",&n,&m,&q)==3) {
        if (!n&&!m&&!q) break; T++;
        memset(head,0,sizeof(head)); cnt=0;
        for (re int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read();
        Kruskal();
        if (T>1) putchar('\n');
        printf("Case #%d\n",T);
        while (q--) {
            int a=read(),b=read();
            int k=Dfs(a,b,0,0);
            if (k==-1) puts("no path");
            else printf("%d\n",k);
        }
    }
    return 0;
}