记录编号	132224	评测结果	AAAAAAAAAAAATTTTTTTT
题目名称	[NOIP 2013]货车运输	最终得分	60
用户昵称	Vincent	是否通过	未通过
代码语言	C++	运行时间	8.462 s
提交时间	2014-10-25 17:34:44	内存使用	14.77 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAXN 10010
#define MAXM 50000
#define INF (1<<30)
#define MIN(A,B) ((A)<(B)?(A):(B))
using namespace std;

vector<int> G[MAXN],F[MAXN];
int u[MAXM],v[MAXM],w[MAXM],p[MAXN];
int n,m,vis[MAXN];

int cmp(const int i, const int j){
    return w[i]>w[j];
}

int findset(int x){
    return p[x]==x ? x : p[x]=findset(p[x]);
}

void Kruskal (){
    int e,x,y,r[MAXM];
    scanf ("%d%d",&n, &m);
    for (int i=0; i<m; ++i)
        scanf ("%d%d%d",u+i,v+i,w+i);
    for (int i=1; i<=n; ++i ) p[i]=i;
    for (int i=0; i<m; ++i) r[i]=i;
    sort (r, r+m, cmp);
    for (int i=0; i<m; ++i){
        e= r[i];
        x= findset(u[e]);
        y= findset(v[e]);
        if (x!=y){
            G[u[e]].push_back(v[e]);
            G[v[e]].push_back(u[e]);
            F[u[e]].push_back(w[e]);
            F[v[e]].push_back(w[e]);
            p[x]=y;
        }
    }
}

int dfs(int ui,int vi,int wi){
    int t=0;
    vis[ui]=1;
    if (ui==vi) return wi;
    for (int i=0; i<G[ui].size(); ++i){
        if( !vis[ G[ui][i] ] )
            t = dfs(G[ui][i],vi,MIN(wi,F[ui][i]));
        if( t ) break;
    }
    return t;
}

int main(){
    int k,x,y;
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    Kruskal();
    scanf ("%d",&k);
    for (int i=0;i<k; ++i){
        scanf ("%d%d",&x,&y);
        memset(vis,0,sizeof(vis));
        if (G[x].size()==0 || G[y].size()==0)
            printf("-1\n");
        else
            printf("%d\n",dfs(x,y,INF));
    }
    return 0;
}