# 洛谷1967 货车运输（noip2013）

Posted by yjjr's blog on February 6, 2018

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

4 3

1 2 4

2 3 3

3 1 1

3

1 3

1 4

1 3

3

-1

3

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxm=5e5+6,maxn=1e5+6,inf=0x3f3f3f;
struct edge{ll u,v,w;}e[maxm];
struct redge{ll to,next,w;}re[maxm];
bool vis[maxm];
inline bool cmp(edge x,edge y){return x.w>y.w;}
inline int find(int x){return x==fastart[x]?fastart[x]:fastart[x]=find(fastart[x]);}

void dfs(int x)
{
vis[x]=1;
rep(i,1,16){
if(depth[x]<(1<<i))break;
fa[x][i]=fa[fa[x][i-1]][i-1];
d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);
}
reg(x){
if(vis[re[i].to])continue;
fa[re[i].to][0]=x;
d[re[i].to][0]=re[i].w;
depth[re[i].to]=depth[x]+1;
dfs(re[i].to);
}
}

inline int lca(int x,int y)
{
if(depth[x]<depth[y])swap(x,y);
int t=depth[x]-depth[y];
rep(i,0,16)if((1<<i)&t)x=fa[x][i];
dep(i,16,0)
if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
if(x==y)return x;
return fa[x][0];
}

{
int re=inf,t=depth[x]-depth[father];
rep(i,0,16)
if((1<<i)&t){
re=min(re,d[x][i]);
x=fa[x][i];
}
return re;
}
int main()
{
mem(d,inf);
sort(e+1,e+1+m,cmp);
rep(i,1,n)fastart[i]=i;
rep(i,1,m){
int r1=find(e[i].u),r2=find(e[i].v);
if(r1!=r2){
fastart[r1]=r2;
}
if(cnt==2*(n-1))break;
}
rep(i,1,n)if(!vis[i])dfs(i);