ACM-ICPC 2016 沈阳赛区现场赛 I. The Elder && HDU 5956（斜率DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5956

题意：一颗树上每条边有个权值，每个节点都有新闻要送到根节点就是1节点，运送过程中如果不换青蛙就是走过的所有边权之和的平方，如果换就每次更换要加上P，也就是求“每个节点到根节点这段路径切分成几块之后 [每块的权值和的平方加上(块个数-1)*P] 的最小值”。然后找到所有节点中消耗最大的那个是多少。

题解：设 dist[ i ] 表示节点 i 到根节点的距离，有 dp[ i ] = min（dp[ j ] + ( dist[ i ] - dist[ j ] ) ^ 2 + p），显然是斜率dp，需要注意的是这是在树上做斜率dp，当遍历了一个节点的某一棵子树后，遍历该节点的下一棵子树要恢复到之前的状态，可以考虑 dfs 过程中多传两个参数代表当前队列的 head 和 tail，而遍历完一棵子树后可能改变的是 tail，所以在比遍历之前把 tail 的节点记录下来即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 1e5 + ;

 const int MAXM = 1e3 + ;

 const ll mod = ;

 int n;

 ll p,ans;

 vector<pair<int,ll> >vec[MAXN];

 ll dist[MAXN],dp[MAXN];

 int q[MAXN];

 ll sqr(ll x) {

     return x * x;

 }

 ll getup(int j,int k) {

     return dp[j] + sqr(dist[j]) - (dp[k] + sqr(dist[k]));

 }

 ll getdown(int j,int k) {

     return 2ll * (dist[j] - dist[k]);

 }

 void dfs(int u,int fa,int st,int en) {

     dp[u] = dist[u] * dist[u];

     int head = st, tail = en;

     while(head +  < tail && getup(q[head + ],q[head]) <= dist[u] * getdown(q[head + ],q[head])) head++;

     dp[u] = min(dp[u], dp[q[head]] + sqr(dist[u] - dist[q[head]]) + p);

     while(head +  < tail && getup(u,q[tail - ]) * getdown(q[tail - ],q[tail - ]) <= getup(q[tail - ],q[tail - ]) * getdown(u,q[tail - ]))

         tail--;

     q[tail++] = u;

     int pre = u;

     ans = max(ans, dp[u]);

     for(int i = ; i < vec[u].size(); i++) {

         int v = vec[u][i].first;

         ll w = vec[u][i].second;

         if(v == fa) continue;

         dist[v] = dist[u] + w;

         dfs(v,u,head,tail);

     }

     q[tail - ] = pre;

 }

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 #endif

     int t;

     scanf("%d",&t);

     while(t--) {

         scanf("%d%lld",&n,&p);

         for(int i = ; i <= n; i++) {

             vec[i].clear();

         }

         for(int i = ; i < n; i++) {

             int u,v;

             ll w;

             scanf("%d%lld%lld",&u,&v,&w);

             vec[u].push_back(make_pair(v,w));

             vec[v].push_back(make_pair(u,w));

         }

         dist[] = ;

         int head = , tail = ;

         q[tail++] = ;

         ans = ;

         dfs(,,,);

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

ACM-ICPC 2016 沈阳赛区现场赛 I. The Elder && HDU 5956（斜率DP）

最新文章

热门文章