As we know, the price of this book was different in each city. It is a i ai yuan yuan in i i t t city. Kelukin will take taxi, whose price is 1 1 yuan yuan per km and this fare cannot be ignored.
There are n−1 n−1 roads connecting n n cities. Kelukin can choose any city to start his travel. He want to know the maximum money he can get.
InputThe first line contains an integer T T
(1≤T≤10 1≤T≤10
) , the number of test cases.
For each test case:
first line contains an integer n n
(2≤n≤100000 2≤n≤100000
) means the number of cities;
second line contains n n
numbers, the i i
th th
number means the prices in i i
th th
city; (1≤Price≤10000) (1≤Price≤10000)
then follows n−1 n−1
lines, each contains three numbers x x
, y y
and z z
which means there exists a road between x x
and y y
, the distance is z z
km km
(1≤z≤1000) (1≤z≤1000)
.
OutputFor each test case, output a single number in a line: the maximum money he can get.
Sample Input
1 4 10 40 15 30 1 2 30 1 3 2 3 4 10
Sample Output
8
题意：现在有一棵树，每个节点有自己的价格，边之间有运费，问最大差价是多少。
思路：可以树DP。这里用的最长路，没想到啊。 每个点与源点连一个正价，与汇点连一个负价。然后跑最长路，就可以得到最大收益。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int inf=1e9+7; const int maxn=400010; int S,T,a[maxn],Laxt[maxn],Next[maxn],To[maxn],Len[maxn],dis[maxn],in[maxn],cnt; void add(int u,int v,int w){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w; } void read(int &x){ x=0; char c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar(); } void SPFA() { rep(i,0,T) dis[i]=-inf,in[i]=0; dis[S]=0; queue<int>q; q.push(S); in[S]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[u]+Len[i]>dis[v]) { dis[v]=dis[u]+Len[i]; if(!in[v]) in[v]=1,q.push(v); } }in[u]=0; } } int main() { int Case,N,u,v,w; scanf("%d",&Case); while(Case--){ read(N); T=N+1; rep(i,1,N) read(a[i]); rep(i,0,T) Laxt[i]=0; cnt=0; rep(i,1,N-1){ read(u); read(v); read(w); add(u,v,-w); add(v,u,-w); } rep(i,1,N) add(S,i,-a[i]); rep(i,1,N) add(i,T,a[i]); SPFA(); printf("%d ",dis[T]); } return 0; }
数据比较奇葩，普通的SPFA效率比优先队列的高。。。
#include<bits/stdc++.h> #define pii pair<int,int> #define mp make_pair #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int inf=1e9+7; const int maxn=400010; int S,T,a[maxn],Laxt[maxn],Next[maxn],To[maxn],Len[maxn],dis[maxn],cnt; void add(int u,int v,int w){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w; } void SPFA() { rep(i,0,T) dis[i]=-inf; dis[S]=0; priority_queue<pii>q; q.push(mp(-0,S)); while(!q.empty()){ int u=q.top().second; q.pop(); for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[u]+Len[i]>dis[v]) { dis[v]=dis[u]+Len[i]; q.push(mp(-dis[v],v)); } } } } int main() { int C,N,u,v,w; scanf("%d",&C); while(C--){ scanf("%d",&N); T=N+1; rep(i,1,N) scanf("%d",&a[i]); rep(i,0,T) Laxt[i]=0; cnt=0; rep(i,1,N-1){ scanf("%d%d%d",&u,&v,&w); add(u,v,-w); add(v,u,-w); } rep(i,1,N) add(S,i,a[i]); rep(i,1,N) add(i,T,-a[i]); SPFA(); printf("%d ",dis[T]); } return 0; }
树DP，Mn表示经过这个点到子树里买的最小值，Mx表示经过这个点到子树里卖的最大值，每次上传时由于多经过一条边，减去边权更新即可：
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=200010; int Mx[maxn],Mn[maxn]; int Laxt[maxn],Next[maxn],To[maxn],Len[maxn],cnt,ans; void add(int u,int v,int w){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w; } void dfs(int u,int fa){ for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(v!=fa) { dfs(v,u); Mn[u]=min(Mn[v]+Len[i],Mn[u]); Mx[u]=max(Mx[v]-Len[i],Mx[u]); } } ans=max(Mx[u]-Mn[u],ans); } int main() { int T,N,u,v,w; scanf("%d",&T); while(T--){ scanf("%d",&N); rep(i,1,N) Laxt[i]=0; cnt=0; ans=0; rep(i,1,N) scanf("%d",&Mn[i]),Mx[i]=Mn[i]; rep(i,1,N-1){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,0); printf("%d ",ans); } return 0; }