网站ui怎么做的,wordpress pdo mysql扩展,定州网站制作,深圳企业网站建设制作Description A 国有 n 座城市#xff0c;编号从 1 到 n#xff0c;城市之间有 m 条双向道路。每一条道路对车辆都有重量限制#xff0c;简称限重。现在有 q 辆货车在运输货物#xff0c;司机们想知道每辆车在不超过车辆限重的情况下#xff0c;最多能运多重的货物。 Input… Description A 国有 n 座城市编号从 1 到 n城市之间有 m 条双向道路。每一条道路对车辆都有重量限制简称限重。现在有 q 辆货车在运输货物司机们想知道每辆车在不超过车辆限重的情况下最多能运多重的货物。 Input 第一行有两个用一个空格隔开的整数 nm表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行 3 个整数 x、y、z每两个整数之间用一个空格隔开表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意x 不等于 y两座城市之间可能有多条道路。 接下来一行有一个整数 q表示有 q 辆货车需要运货。 接下来 q 行每行两个整数 x、y之间用一个空格隔开表示一辆货车需要从 x 城市运输货物到 y 城市注意x 不等于 y。 Output 输出共有 q 行每行一个整数表示对于每一辆货车它的最大载重是多少。如果货车不能到达目的地输出-1。 Sample Input 4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3 Sample Output 3 -1 3 Hint 对于 30%的数据0 n 1,0000 m 10,0000 q 1,000 对于 100%的数据0 n 10,0000 m 50,0000 q 30,0000 ≤ z ≤ 100,000。 题解 这个题目是找每条路径上的最大边权的最小最大值首先要知道结论图中任意两点路径的最大最小值一定是在这个图的最大生成树上因为我们做克鲁斯卡尔的时候是将边从大到到小排序然后一颗生成树包含了图中任意节点并且因为是从大到小所以所以的边都尽量选最大的那么限制条件——那个最小值一定在树上所以把树扣出来用倍增或者是树链剖分维护一下就可以了。主要对森林的处理用并查集维护同时向一个联通块连一条-1的边。 代码 #includeiostream
#includestdio.h
#includestdlib.h
#includealgorithm
#includecstring
const int MAXN200300;
using namespace std;
int n,m,q,num0,faa[MAXN];
struct edge1{int from,to,quan;void read(){scanf(%d%d%d,from,to,quan);}
}e[MAXN*2];
struct edge3{int from,to,quan;
}h[MAXN*2];
struct edge{int to,quan,first,next;
}a[MAXN*2];
int son[MAXN],size[MAXN],deep[MAXN],fa[MAXN];
int top[MAXN],id[MAXN],w[MAXN],numm;
struct tree{int l,r,minn;
}tr[MAXN*4];void cl(){for(int i1;iMAXN*4-1;i) tr[i].minn130;memset(fa,0,sizeof(fa));memset(son,0,sizeof(son));memset(size,0,sizeof(size));memset(deep,0,sizeof(deep));memset(top,0,sizeof(top));memset(id,0,sizeof(id));memset(w,0,sizeof(w));
}bool comp(edge1 x,edge1 y){if(x.quany.quan) return 1;return 0;
}void addedge(int from,int to,int quan){a[num].toto;a[num].quanquan;a[num].nexta[from].first;a[from].firstnum;
}int find(int now){if(now!faa[now]) faa[now]find(faa[now]);return faa[now];
}void hebin(int x,int y){int hhfind(x),hhhfind(y);faa[hh]hhh;
}void Mtree(){for(int i1;im;i) e[i].read();for(int i1;in;i) faa[i]i;for(int i1;im;i){int xe[i].from,ye[i].to;if(find(x)!find(y)){hebin(x,y);}}for(int i2;in;i){if(find(1)!find(i)){int hhfind(1),yyfind(i);e[m].fromhh,e[m].toyy,e[m].quan-1;hebin(hh,yy);}}sort(e1,em1,comp);for(int i1;in;i) faa[i]i;numm0;for(int i1;im;i){int xe[i].from,ye[i].to,ze[i].quan;int xxfind(x);int yyfind(y);if(xx!yy){numm;hebin(x,y);addedge(x,y,z),addedge(y,x,z);h[numm].fromx,h[numm].toy,h[numm].quanz;}if(nummn-1) break;}
}void dfs1(int now,int f){fa[now]f;size[now]1;deep[now]deep[f]1;for(int ia[now].first;i;ia[i].next){int toa[i].to;if(tof) continue;dfs1(to,now);size[now]size[to];if(size[son[now]]size[to]) son[now]to;}
}void dfs2(int now,int rf){top[now]rf;id[now]num;if(son[now]) dfs2(son[now],rf);for(int ia[now].first;i;ia[i].next){int toa[i].to;if(tofa[now]||toson[now]) continue;dfs2(to,to);}
}void build(int xv,int l,int r){if(lr){tr[xv].ll,tr[xv].rr;if(l1) return;tr[xv].minnw[l];return;}tr[xv].ll,tr[xv].rr;int mid(lr)/2;build(xv*2,l,mid);build(xv*21,mid1,r);tr[xv].minnmin(tr[xv*2].minn,tr[xv*21].minn);
}int kanxun(int xv,int l,int r){int Ltr[xv].l,Rtr[xv].r,mid(LR)/2;if(lLrR){return tr[xv].minn;}if(rmid) return kanxun(xv*2,l,r);else if(lmid) return kanxun(xv*21,l,r);else return min(kanxun(xv*2,l,mid),kanxun(xv*21,mid1,r));
}int getmin(int x,int y){int topxtop[x],topytop[y],minn130;while(topx!topy){if(deep[topx]deep[topy]) swap(x,y),swap(topx,topy);minnmin(kanxun(1,id[topx],id[x]),minn);xfa[topx],topxtop[x];}if(xy) return minn;if(deep[x]deep[y]) swap(x,y);minnmin(minn,kanxun(1,id[son[y]],id[x]));return minn;
}int main(){cl();scanf(%d%d,n,m);Mtree();memset(fa,0,sizeof(fa));dfs1(1,0);num0;dfs2(1,1);for(int i1;inumm;i){if(deep[h[i].from]deep[h[i].to]) swap(h[i].from,h[i].to);int toh[i].to,quanh[i].quan;w[id[to]]quan;}build(1,1,num);scanf(%d,q);for(int i1;iq;i){int x,y;scanf(%d%d,x,y);printf(%d\n,getmin(x,y));}
} 转载于:https://www.cnblogs.com/renjianshige/p/7231849.html
