首页 > ACM题库 > HDU-杭电 > HDU 3057-Core-动态规划-[解题报告]HOJ
2014
03-01

HDU 3057-Core-动态规划-[解题报告]HOJ

Core

问题描述 :

Suppose T=<V,E,W> is an acyclic, connected, undirected graph(or we can call it unrooted tree), each edge has a positive weigh, we call this graph Tree Network. (V is the vertex set, E is edge set, and W is weigh set).

In the Tree Network, each pair of vertex u, v has a simple path, then the distance from u to v, written as d(u,v), is the length of a u,v-path.

Another definition is d(V,x), d(V,x)=min{d(v,x)|v∈V}.

Suppose any connected subgraph of T is T’=(V’,E’,W’), We called ECC(T’,T)=max{d(V’,u)|u∈(V-V’)} is the eccentricity of T’.

Now is your turn, give you a Tree Network T and a non-negative integer S, you must find a connected subgraph of T ―― T’, which satisfy the sum all of the edges weigh in T’ is not bigger than S and the eccentricity of T’ is the least than other subgraph of T. We called the T’ “Core of Tree Network”

Notice: Sometimes, T’ only contains one vertex, and you may find there are many cores. But we only want to know the minimal eccentricity of T’, and that is determinately.

输入:

Input includes multiple cases.

First line is the number of case x.

For each case:

The first line includes two integer numbers. N (1<=N<=10000) and S(1<=S<=108).

The other n-1 lines describe the edges in T.

Each line contains three positive integer numbers u,v,w(1<=u,v,w<=10000), describe the head, the endpoints and the weigh of an edge.

输出:

Input includes multiple cases.

First line is the number of case x.

For each case:

The first line includes two integer numbers. N (1<=N<=10000) and S(1<=S<=108).

The other n-1 lines describe the edges in T.

Each line contains three positive integer numbers u,v,w(1<=u,v,w<=10000), describe the head, the endpoints and the weigh of an edge.

样例输入:

2
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
5 9
1 2 5
2 3 2
2 4 4
2 5 3 

样例输出:

5
3 

     思路:

         dp[i]=min{dp[j]+(sum[i]-sum[j])^2+M}(dp[i]表示前i个字的花费,0<j<=i-1)

   AC代码:

#include<stdio.h>
#define N  500010
int dp[N];
int q[N];
int head,tail;
int sum[N];
int a[N];
int n,m;
int getDP(int i,int j)
{
    return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
}
int getUP(int j,int k)
{
    return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);
}
int getDOWN(int j,int k)
{
   return  2*(sum[j]-sum[k]);
}
int main()
{
	int i;
	while(scanf("%d%d",&n,&m)!=-1)
	{
       sum[0]=0;
	   for(i=1;i<=n;i++)
	   {
		   scanf("%d",&a[i]);
		   sum[i]=sum[i-1]+a[i];
	   }
       head=tail=0;
	   q[tail++]=0;
	   dp[0]=0;
	   for(i=1;i<=n;i++)
	   {
	      while(head+1<tail&&getUP(q[head+1],q[head])<=sum[i]*getDOWN(q[head+1],q[head]))
			  head++;
		  dp[i]=getDP(i,q[head]);
		  while(head+1<tail&&getUP(q[tail-1],q[tail-2])*getDOWN(i,q[tail-1])>=getUP(i,q[tail-1])*getDOWN(q[tail-1],q[tail-2]))
		  tail--;
		  q[tail++]=i;
	   }
	   printf("%d\n",dp[n]);
	}
    return 0;
}

参考:http://blog.csdn.net/job_yi/article/details/9880711


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯