1519 過路費
時間限制: 1 s
空間限制: 256000 KB
題目等級 : 大師 Master
題目描述 Description
在某個遙遠的國家里，有 n個城市。編號為 1,2,3,…,n。這個國家的政府修建了m 條雙向道路，每條道路連接著兩個城市。政府規定從城市 S 到城市T需要收取的過路費為所經過城市之間道路長度的最大值。如：A到B長度為 2，B到C 長度為3，那么開車從 A經過 B到C 需要上交的過路費為 3。
佳佳是個做生意的人，需要經常開車從任意一個城市到另外一個城市，因此他需要頻繁地上交過路費，由于忙于做生意，所以他無時間來尋找交過路費最低的行駛路線。然而， 當他交的過路費越多他的心情就變得越糟糕。 作為秘書的你，需要每次根據老板的起止城市，提供給他從開始城市到達目的城市，最少需要上交多少過路費。
輸入描述 Input Description
第一行是兩個整數 n 和m，分別表示城市的個數以及道路的條數。
接下來 m 行，每行包含三個整數 a，b，w（1≤a，b≤n，0≤w≤10^9），表示a與b之間有一條長度為 w的道路。
接著有一行為一個整數 q，表示佳佳發出的詢問個數。
再接下來 q行，每一行包含兩個整數 S，T（1≤S,T≤n，S≠T）, 表示開始城市S 和目的城市T。
輸出描述 Output Description
輸出共q行，每行一個整數，分別表示每個詢問需要上交的最少過路費用。輸入數據保證所有的城市都是連通的。
樣例輸入 Sample Input
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
樣例輸出 Sample Output
20
20
數據范圍及提示 Data Size & Hint
對于 30%的數據，滿足 1≤ n≤1000，1≤m≤10000，1≤q≤100；
對于 50%的數據，滿足 1≤ n≤10000，1≤m≤10000，1≤q≤10000；
對于 100%的數據，滿足 1≤ n≤10000，1≤m≤100000，1≤q≤10000；
分類標簽 Tags
分治 最小生成樹 圖論

/* Slf(spfa優化). 50棄療了. 跑最小生成樹后Slf. 有一個鏈的測試點卡不過去. （不搞mst的話還是能卡過去的）. 論常數的重要性orz. */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define MAXN 100001 using namespace std; int head[MAXN],n,m,k,cut,father[MAXN],tot,dis[MAXN],q[MAXN]; struct edge{int v,next;int x;}e[MAXN*2]; struct data{int x,y,z;}s[MAXN*2]; bool b[MAXN]; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x; } int ffind(int x) {return x!=father[x]?father[x]=ffind(father[x]):x; } void add(int u,int v,int z) {e[++cut].v=v;e[cut].x=z;e[cut].next=head[u];head[u]=cut; } bool cmp(const data &x,const data &y) {return x.z<y.z; } int spfa(int s,int t) {int u,v;int head1=1,tail=1;for(int i=1;i<=n;i++) dis[i]=1e10,b[i]=false;q[head1]=s;dis[s]=0;while(head1<=tail){u=q[head1++];b[u]=false;if(head1>n+1) head1=1;for(int i=head[u];i;i=e[i].next){v=e[i].v;if(dis[v]>max(dis[u],e[i].x)){dis[v]=max(dis[u],e[i].x);if(!b[v]){b[v]=true;if(dis[v]>dis[q[head1]]){if(--head1<0) head1=n;q[head1]=v;}else {q[++tail]=v;if(tail>n+1) tail=1;}}}}}return dis[t]; } int main() {int x,y,z;n=read(),m=read();for(int i=1;i<=n;i++) father[i]=i;for(int i=1;i<=m;i++)x=read(),y=read(),z=read(),s[i].x=x,s[i].y=y,s[i].z=z;sort(s+1,s+m+1,cmp);for(int i=1;i<=m;i++){x=ffind(s[i].x),y=ffind(s[i].y);if(x!=y){tot++;father[x]=y;add(s[i].x,s[i].y,s[i].z);add(s[i].y,s[i].x,s[i].z);}if(tot==n-1) break;}k=read();while(k--){x=read(),y=read();printf("%d\n",spfa(x,y));}return 0; } /* mst定理:最小生成樹里的最長邊最短. 然后lca維護兩點距離. 還有不要漏下某種情況. */ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define MAXN 100001 #define D 21 using namespace std; int head[MAXN],n,m,k,cut,father[MAXN],tot,st,fa[MAXN][D+5],deep[MAXN],dis[MAXN][D+5]; struct edge{int v,next;int x;}e[MAXN*2]; struct data{int x,y,z;}s[MAXN*2]; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x; } int ffind(int x) {return x!=father[x]?father[x]=ffind(father[x]):x; } void add(int u,int v,int z) {e[++cut].v=v;e[cut].x=z;e[cut].next=head[u];head[u]=cut; } bool cmp(const data &x,const data &y) {return x.z<y.z; } void dfs(int u,int f,int d) {deep[u]=d+1;for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(f!=v){fa[v][0]=u;dis[v][0]=e[i].x;dfs(v,u,d+1);}}return ; } void get_father() {for(int j=1;j<=D;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1],dis[i][j]=max(dis[fa[i][j-1]][j-1],dis[i][j-1]);return ; } int get_same(int u,int v) {for(int i=0;i<=D;i++){if((1<<i)&v){tot=max(tot,dis[u][i]);u=fa[u][i];}}return u; } int lca(int u,int v) {tot=0;if(deep[v]>deep[u]) swap(u,v);u=get_same(u,deep[u]-deep[v]);if(u==v) return tot;for(int i=D;i>=0;i--){if(fa[u][i]!=fa[v][i]){tot=max(tot,max(dis[u][i],dis[v][i]));u=fa[u][i];v=fa[v][i];}}tot=max(tot,max(dis[u][0],dis[v][0]));return tot; } int main() {int x,y,z;n=read(),m=read();for(int i=1;i<=n;i++) father[i]=i;for(int i=1;i<=m;i++)x=read(),y=read(),z=read(),s[i].x=x,s[i].y=y,s[i].z=z;sort(s+1,s+m+1,cmp);for(int i=1;i<=m;i++){x=ffind(s[i].x),y=ffind(s[i].y);if(x!=y){tot++;father[x]=y;add(s[i].x,s[i].y,s[i].z);add(s[i].y,s[i].x,s[i].z);}if(tot==n-1) break;}dfs(1,1,0);get_father();k=read();while(k--){x=read(),y=read();printf("%d\n",lca(x,y));}return 0; }

轉載于:https://www.cnblogs.com/nancheng58/p/10068172.html

總結

以上是生活随笔為你收集整理的Codevs 1519 过路费(Mst+Lca)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。