Текущ брой на Списание ИнфоМан
 


Международна олимпиада по информатика 2005, Задача 2.3. RIVERS

Уловието на задачата може да прочетете тук.

Решение

За всеки връх vв дървото с линейна сложност могат да се определят следните стойности:

depth(v) – на каква дълбочина е разположен;

dist(v) – на какво разстояние е от връх номер 0;

trees(v) – колко върха има в поддървото с корен дадения връх.

За да се реши задачата може да се приложи методът на динамичното оптимиране. Дефинираме функция A[v,l,t], която за дадено поддърво с корен vпресмята най-малката цена, за да се разположат tдъскорезници, като дърветата, които достигат до корена v, ще се обработват във върха wнадолу по реката, за който depth(w) = l.

Очевидно A[v,l,t]за връх v, за който trees(v) = t,е равно на 0. Общата формула за пресмятане на A[v,l,t]е следната:

A[v,l,t] = 0 ако trees(v) = tи

A[v,l,t] = min(m1, m2), където m1е цената за транспортиране, когато няма дъскорезница във върха v, a m2 е цената за транспортиране, когато има.

Нека vима dпреки наследника v1,v2,..,vd, а върха, които се намира на дълбочина l, означим с w. Тогава m1и m2се пресмятат по следните формули:

m1 = trees(v)*(dist(v) – dist(w)) + min Σ A[vi,l,ti],където 1idи t1+ t2+…+ td = t;

m2 = min Σ A[vi,depth(v),ti], където 1idи t1+ t2+…+ td = t-1

С t1, t2,…, t dе обозначен броят на дъскорезниците, които са построени във всяко от поддърветата, чиито корени са преките наследници на върха v.

Този подход може да е много неефективен ако в дървото има достатъчно много върхове с голям брой преки наследници. За целта от даденото дърво може да се построи ново, което да има същата минимална цена за транспортиране на всички дървета. Това дърво е двоично и така всеки връх има максимум два наследника, което е достатъчно малко. Дървото се игражда по следната логика: За всеки връх vот началното дърво първият му наследник се поставя като ляв наследник в новото дърво, а за десен се създава нов връх, за който реката, която го свързва с родителя му има дължина 0 и в този нов връх се отсичат 0 дървета. Следващият от наследниците на vсе поставя като ляв наследник на току що построения нов връх и отново се поставя един нов връх като десен наследник и по този начин в дървото се поставят всички преки наследници на v.

Това се прави за всички върхове от началното дърво. Получава се двоично дърво с максимум 2 пъти повече върха от началното, защото всеки връх добавя най-много още един в новото дърво. А минималната цена за това дърво за транспортиране е същата като тази за началното, понеже ако има някакво разположение, което използва новодобавените върхове, за да построи дъскорезница, то тази дъскорезница може да се разположи до първия връх нагоре по дървото, който е съществувал и в началното. За всички двойки връх – дълбочина (v,l)трябва да се пресметнат стойностите за всички възможни броеве дъскорезници, които да се поставят в съотвеното поддърво, което има сложност O(k2), следователно цялата сложност е O(n2k2).

Примерна реализация


#include <stdio.h>

#define MAXN		128
#define MAXK		64

#define INF			2000000000

struct tnasl
{
	int nasl;
	int dist;
};

int n,k;
// the chldren in the tree from the input
tnasl nasl[MAXN][MAXN];
// the number of the children for each vertice in the tree
int brn[MAXN];
// the number of trees cut in each vertice
int trcut[2*MAXN];
// the two children in the new tree constructed
tnasl ch[2*MAXN][2];
// the order in which the vertices are processed in the dp
int order[2*MAXN];
int curnum;
// the depth of each vertice
int rdepth[2*MAXN];
// the level of each vertice in the tree
int depth[2*MAXN];
// the number of vertices in each subtree
int numch[2*MAXN];
// the parent of each vertice in the new tree
int par[2*MAXN];
// the table for the dynamic programming (dp)
int dp[2*MAXN][2*MAXN][MAXK];
int ans;

void DFS(int num, int realdep, int dep)
{
	// order of vertices in which they are traverced
	order[curnum++] = num;
	// computing the depth of the node
	rdepth[num] = realdep;
	// computing the level of the node
	depth[num] = dep;
	
	// if there are children of this node
	if(ch[num][0].nasl!=0)
	{
		// DFS for the left node
		DFS(ch[num][0].nasl, realdep+ch[num][0].dist, dep+1);
		// DFS for the right node
		DFS(ch[num][1].nasl, realdep+ch[num][1].dist, dep+1);
		// computing the number of vertices 
		numch[num] = numch[ch[num][0].nasl] + numch[ch[num][1].nasl];
	}
	// if this is a leaf
	else
	{
		numch[num] = 1;
	}
}

int minv(int a, int b)
{
	return (a<b)?a:b;
}

void input()
{
	int i;
	int parent,dist;

	scanf("%d %d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d %d",&trcut[i],&parent,&dist);
		nasl[parent][brn[parent]].nasl = i;
		nasl[parent][brn[parent]].dist = dist;
		brn[parent]++;
	}
}

void solve()
{
	int i,i2,i3,i4;
	int lastu;
	int curn;
	int min1,min2;
	int ch1,ch2;
	int trgoto;

	lastu = n+1;

	par[0] = -1;

	// creating the new tree
	for(i=0;i<=n;i++)
	{
		curn = i;
		for(i2=0;i2<brn[i];i2++)
		{
			ch[curn][0] = nasl[i][i2];
			ch[curn][1].nasl = lastu;
			ch[curn][1].dist = 0;
			trcut[lastu] = 0;
			par[nasl[i][i2].nasl] = curn;
			par[lastu] = curn;
			curn = lastu;
			lastu++;
		}
	}

	curnum = 0;
	DFS(0,0,0);

	// check all the vertices
	for(i=curnum-1;i>0;i--)
	{
		curn = order[i];
		ch1 = ch[curn][0].nasl;
		ch2 = ch[curn][1].nasl;

		// check all the vertices where the left trees
		// are caugth
		trgoto = curn;
		for(i2=depth[curn]-1;i2>=0;i2--)
		{
			trgoto = par[trgoto];
			if(numch[curn]<=k)
				dp[curn][i2][numch[curn]] = 0;

			// check all the possible numbers of additional
			// mills to be added
			for(i3=0;i3<numch[curn]&&i3<=k;i3++)
			{
				min1 = min2 = INF;

				// check all the possible numbers 
				// of mills added in the left subtree
				for(i4=0;i4<=i3;i4++)
				{
					if(min1 > dp[ch1][i2][i4]+
					dp[ch2][i2][i3-i4])
						min1 = dp[ch1][i2][i4]+
						dp[ch2][i2][i3-i4];

					if(i3-i4-1>=0)
					
						if(min2 > 
						dp[ch1][depth[curn]][i4]+
						dp[ch2][depth[curn]]
						[i3-i4-1])
							
						min2 = 
						
						dp[ch1]
						[depth[curn]][i4]
						
						+
						
						dp[ch2]
						[depth[curn]]
						[i3-i4-1];
						
				}

				// add the value for transporting the 
				// left trees up the river
				min1 += trcut[curn]*
				(rdepth[curn]-rdepth[trgoto]);

				dp[curn][i2][i3] = minv(min1,min2);
			}
		}
	}

	ans = INF;
	ch1 = ch[0][0].nasl;
	ch2 = ch[0][1].nasl;

	// calculate the minimum value for the root of the tree
	for(i=0;i<=k;i++)
	{
		if(ans>dp[ch1][0][i]+dp[ch2][0][k-i])
			ans = dp[ch1][0][i]+dp[ch2][0][k-i];
	}
}

void output()
{
	printf("%d\n",ans);
}

int main()
{
	//freopen("riv.inp","r",stdin);
	//freopen("riv.out","w",stdout);

	input();
	solve();
	output();

	return 0;
}


Автор: Антон Димитров


обратно към брой 27