一开始觉得是网络流..仔细一看应该是最短路，再看数据范围..呵呵不会写...这道题是最大生成树+最近公共祖先。第一次写..表示各种乱..
因为要求运输货物质量最大，所以路径一定是在最大生成树上的。然后就用LCA求两点之间的能运输的最大重量。预处理O(nlogn),查询O(logn).
----------------------------------------------------------------------------------------
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cctype>
#define rep(i,n) for(int i=0;i<n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define Rep(i,l,r) for(int i=l;i<r;i++)
#define addEdge(u,v,d) MST.edges.push_back((Edge){u,v,d})
#define jud(a,b) MST.find(a)-MST.find(b)
using namespace std;
const int maxn=10000+5,maxs=20;
const int inf=0x7fffffff;
struct Edge {
int u,v,d;
Edge(int _u,int _v,int _d):u(_u),v(_v),d(_d) {}
bool operator < (const Edge &x) const {
return d>x.d;
}
};
struct LCA {
int p[maxn][maxs];
int depth[maxn];
int d[maxn][maxs];
bool vis[maxn];
int n;
vector<int> g[maxn];
vector<Edge> edges;
void init(int _n) {
n=_n;
edges.clear();
rep(i,n) { g[i].clear(); vis[i]=false; }
}
void add(int u,int v,int d) {
edges.push_back( (Edge) {u,v,d} );
edges.push_back( (Edge) {v,u,d} );
int m=edges.size();
g[u].push_back(m-2);
g[v].push_back(m-1);
}
void dfs(int x) {
int t=1;
vis[x]=1;
while(depth[x]>=(1<<t)) {
p[x][t]=p[p[x][t-1]][t-1];
d[x][t]=min(d[x][t-1],d[p[x][t-1]][t-1]);
t++;
}
rep(i,g[x].size()) {
Edge &e=edges[g[x][i]];
if(vis[e.v]) continue;
p[e.v][0]=x;
d[e.v][0]=e.d;
depth[e.v]=depth[x]+1;
dfs(e.v);
}
}
void DFS() { rep(i,n) if(!vis[i]) { depth[i]=0; dfs(i); } }
int query(int a,int b) {
int tmp,log=1;
if(depth[a]<depth[b]) swap(a,b);
while((1<<(log+1))<=depth[a]) log++;
int ans=inf;
for(int i=log;i>=0;--i) if(depth[a]-(1<<i)>=depth[b]) {
ans=min(ans,d[a][i]);
a=p[a][i];
}
if(a==b) return ans;
for(int i=log;i>=0;--i) if(p[a][i]!=-1 && p[a][i]!=p[b][i]) {
ans=min(ans,d[a][i]); a=p[a][i];
ans=min(ans,d[b][i]); b=p[b][i];
}
return ans=min(ans,min(d[a][0],d[b][0]));
}
};
LCA lca;
struct KRUSKAL {
int n;
int p[maxn];
vector<Edge> edges;
void init(int _n) {
n=_n;
edges.clear();
}
int find(int x) { return x==p[x] ? x : p[x]=find(p[x]); }
void kruskal() {
rep(i,n) p[i]=i;
sort(edges.begin(),edges.end());
rep(i,edges.size()) {
Edge &e=edges[i];
int x=find(e.u),y=find(e.v);
if(x!=y) {
p[x]=y;
lca.add(e.u,e.v,e.d);
}
}
}
};
KRUSKAL MST;
int read() {
char c=getchar();
int ans=0,f=1;
while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)) { (ans*=10)+=c-'0'; c=getchar(); }
return f*ans;
}
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n=read(),m=read();
MST.init(n);
lca.init(n);
rep(i,m) {
int u=read(),v=read(),d=read();
addEdge(--u,--v,d);
}
MST.kruskal();
lca.DFS();
n=read();
rep(i,n) {
int a=read(),b=read();
--a; --b;
if(jud(a,b)) printf("-1\n");
else {
printf("%d\n",lca.query(a,b));
}
}
return 0;
}
----------------------------------------------------------------------------------------
3287 货车运输
2013年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。接下来一行有一个整数 q，表示有 q 辆货车需要运货。接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。 输出描述 Output Description
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
样例输入 Sample Input
4 3
1 2 4 2 3 3 3 1 1 31 3 1 4 1 3 样例输出 Sample Output
3
-13 数据范围及提示 Data Size & Hint
对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000； 对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。