vijos1843（货车运输）

每个货车可以运输的最大货物量就是起点到终点的某一条路径上的最小权值，为了使运输量最大，那就是选一条路使得这条路上的最小权值边最大。

于是想到最大生成树，然后就是树上查询两点之间路径上的最小值，熟练剖分可以解。

#include 
#include 
#include 
#include 
using namespace std;
#define Del(a,b) memset(a,b,sizeof(a))
const int N = 10005;
int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N];
int num;
vector v[N];
struct Edge{int from;int to;int w;bool operator < (const Edge& T) const{return w>T.w;}
}ed[50000+50];
struct tree
{int x,y,val;void read(int a,int b,int c){x = a; y = b; val = c;}
};
tree e[N];
void dfs1(int u, int f, int d) {dep[u] = d;siz[u] = 1;son[u] = 0;fa[u] = f;for (int i = 0; i < v[u].size(); i++) {int ff = v[u][i];if (ff == f) continue;dfs1(ff, u, d + 1);siz[u] += siz[ff];if (siz[son[u]] < siz[ff])son[u] = ff;}
}
void dfs2(int u, int tp) {top[u] = tp;id[u] = ++num;if (son[u]) dfs2(son[u], tp);for (int i = 0; i < v[u].size(); i++) {int ff = v[u][i];if (ff == fa[u] || ff == son[u]) continue;dfs2(ff, ff);}
}
#define lson(x) ((x<<1))
#define rson(x) ((x<<1)+1)
struct Tree
{int l,r,val;
};
Tree tree[4*N];
void pushup(int x) {tree[x].val = min(tree[lson(x)].val, tree[rson(x)].val);
}
void build(int l,int r,int v)
{tree[v].l=l;tree[v].r=r;if(l==r){tree[v].val = val[l];return ;}int mid=(l+r)>>1;build(l,mid,v*2);build(mid+1,r,v*2+1);pushup(v);
}
int query(int x,int l, int r)
{if (tree[x].l >= l && tree[x].r <= r) {return tree[x].val;}int mid = (tree[x].l + tree[x].r) / 2;int ans = 0x3f3f3f3f;if (l <= mid) ans = min(ans, query(lson(x),l,r));if (r > mid) ans = min(ans, query(rson(x),l,r));return ans;
}
int Yougth(int u, int v) {int tp1 = top[u], tp2 = top[v];int ans = 0x3f3f3f3f;while (tp1 != tp2) {if (dep[tp1] < dep[tp2]) {swap(tp1, tp2);swap(u, v);}ans = min(query(1,id[tp1], id[u]), ans);u = fa[tp1];tp1 = top[u];}if (u == v) return ans;if (dep[u] > dep[v]) swap(u, v);ans = min(query(1,id[son[u]], id[v]), ans);return ans;
}
int par[10000+10];
int find(int u)
{if(u==par[u]) return u;return par[u] = find(par[u]);
}
int main()
{int n,m;memset(val,0x3f3f3f3f,sizeof(val));scanf("%d%d",&n,&m);for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！