2013
12-23

Intermediate Rounds for Multicasting

Consider a communication network consisting of N nodes numbered from 1 to N. The nodes are interconnected in such a way that the network has the shape of a rooted tree, with node 1 as the root. Node 1 wants to send a message (the same message) to each node which is a leaf in the tree (i.e. has no sons) � this operation is known as multicast. A message can only be sent from one node to one of its descendants (including the node itself). Each edge of the tree has an associated cost and the cost of sending a message from a node X to one of its descendants Y is the sum of the costs of the edges on the unique path from X to Y (if X=Y, then the cost is 0). The total cost of a multicast strategy is the sum of the costs of sending each message.
In order to reach its goal, node 1 will use the following multicast strategy: The strategy consists of K intermediate rounds. In the first round, node 1 sends an individual message to a subset of nodes S1 such that each leaf is a descendant of exactly one node X in S1 (this means that any node X in S1 is not a descendant of another node Y in S1). In round i (2<=i<=K), each node X in Si-1 sends an individual message to a subset Si,X of nodes from its subtree, such that each leaf which is a descendant of X is also a descendant of exactly one node in Si,X. The set of nodes Si is the union of the sets Si,X, for each X in Si-1. In the end, each node X in Sk must send a message to each leaf node which is a descendant of X.
Given the communication network, the cost of each edge and the number of intermediate rounds K, find the minimum total cost of a multicast strategy.

The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 2 integer numbers: N (1<=N<=333) and K (1<=K<=10). The next N-1 lines contain 3 integers each: A, B and C (1<=C<=10.000), meaning that node B is a son of node A and the edge (A,B) has cost C.

For each of the T test cases, in the order given in the input, print one line containing the minimum total cost of a multicast strategy having the specified properties.

1
6 1
1 2 10
1 3 11
2 4 21
2 5 17
3 6 7

66

HintIn the first (and only) intermediate round, node 1 sends messages to node 6 (with cost 18) and to node 2 (with cost 10).
So the set S1 is {2,6}. In the end, node 6 will send a message to itself (with cost 0) and node 2 will send messages to node 4 (with cost 21)
and to node 5 (with cost 17). The total cost is 18+10+21+17=66.



/*状态方程为dp[j]=max(dp[j],dp[j-1]+money[i]);

#include <stdio.h>
#include <string.h>

int main()
{
double sum,Q,asum,bsum,csum,price,ans;
double dp[35],money[35];
int n,m,num,i,j,flag;
char ch;
while(scanf("%lf %d",&Q,&n)&&n)
{
num=0;
memset(dp,0,sizeof(dp));
memset(money,0,sizeof(money));
for (i=0;i<n;i++)
{
flag=1;
sum=asum=bsum=csum=0.0;
scanf("%d",&m);
for (j=0;j<m;j++)
{
getchar();
scanf("%c:%lf",&ch,&price);
if(ch!='A'&&ch!='B'&&ch!='C'||price>600.0)
{
flag=0;
break;
}
else if(ch=='A')
asum+=price;
else if(ch=='B')
bsum+=price;
else
csum+=price;
}
sum=asum+bsum+csum;
if(flag&&sum<=1000.0&&asum<=600.0&&bsum<=600.0&&csum<=600.0)
{
money[num]=sum;
num++;
}
}
for (i=0;i<=num;i++)
{
for(j=num;j>=1;j--)
if(j==1||dp[j-1]>0&&dp[j-1]+money[i]<=Q)
dp[j]=dp[j]>(dp[j-1]+money[i])?dp[j]:(dp[j-1]+money[i]);
}
ans=0.0;
for(i=0;i<=num;i++)
if(ans<dp[i])
ans=dp[i];
printf("%.2lf\n",ans);
}
return 0;
}

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

2. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

3. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}