首页 > 专题系列 > Java解POJ > POJ 1155 TELE [解题报告] Java
2013
11-09

POJ 1155 TELE [解题报告] Java

TELE

问题描述 :

A TV-network plans to broadcast an important football match. Their network of transmitters and users can be represented as a tree. The root of the tree is a transmitter that emits the football match, the leaves of the tree are the potential users and other vertices in the tree are relays (transmitters).

The price of transmission of a signal from one transmitter to another or to the user is given. A price of the entire broadcast is the sum of prices of all individual signal transmissions.

Every user is ready to pay a certain amount of money to watch the match and the TV-network then decides whether or not to provide the user with the signal.

Write a program that will find the maximal number of users able to watch the match so that the TV-network’s doesn’t lose money from broadcasting the match.

输入:

The first line of the input file contains two integers N and M, 2 <= N <= 3000, 1 <= M <= N-1, the number of vertices in the tree and the number of potential users.

The root of the tree is marked with the number 1, while other transmitters are numbered 2 to N-M and potential users are numbered N-M+1 to N.

The following N-M lines contain data about the transmitters in the following form:

K A1 C1 A2 C2 … AK CK

Means that a transmitter transmits the signal to K transmitters or users, every one of them described by the pair of numbers A and C, the transmitter or user’s number and the cost of transmitting the signal to them.

The last line contains the data about users, containing M integers representing respectively the price every one of them is willing to pay to watch the match.

输出:

The first and the only line of the output file should contain the maximal number of users described in the above text.

样例输入:

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

样例输出:

5

解题代码:

/* @author: */
import java.util.*;
import java.util.Scanner;
public class Main{

 static  int[][] dp;
 static int[] offspring;
 static int[] vert;
 static int[] parent;
 static int[] leaf;
 static int n,k;
public static void main(String[] args)
{
 Scanner cin=new Scanner(System.in);
 n=cin.nextInt();
 leaf=new int[n+1];
 offspring=new int[n+1];
 vert=new int[n+1];
 parent=new int[n+1];
 dp=new int[n+1][n+1];
 boolean[] flag=new boolean[n+1];
 int[] left=new int[n+1];
 int[] right=new int[n+1];
 for(int i=0;i<=n;i++)
 for(int j=0;j<=n;j++)
 {
   if(j==0)
    dp[i][j]=0;
   else
    dp[i][j]=-99999999;
 }
 k=cin.nextInt();
 for(int i=0;i< n-k;i++)
 {
   int c=cin.nextInt();
   if(c==0)
    continue;
   int temp=i+1;
   int m=cin.nextInt();
   vert[m]=cin.nextInt();
   left[temp]=m;
   parent[m]=temp;
   offspring[temp]+=1;
   temp=m;
   for(int j=1;j< c;j++)
   {
    m=cin.nextInt();
    right[temp]=m;
    parent[m]=temp;
    offspring[temp]+=2;
    vert[m]=cin.nextInt();
    temp=m;
   }
 }
 for(int i=0;i< k;i++)
 {
   int m=i+n-k+1;
   while(m!=0)
   {
     leaf[m]++;
     m=parent[m];
    }
  }
  for(int i=0;i < k;i++)
   {
    dp[i+n-k+1][1]=cin.nextInt()-vert[i+n-k+1];
    if(offspring[i+n-k+1]==0)
      flag[i+n-k+1]=true;
   }
   while(!flag[1])
   {
    for(int i=1;i<=n;i++)
    {
     if(!flag[i])
     {
      int l=left[i];
      int r=right[i];
      if(l==0&&flag[r]) 
      {
       for(int o=leaf[i];o>=0;o--)
       for(int p=leaf[r];p>=0;p--)
       {
        if(o+p<=leaf[i]&&dp[r][p]+dp[i][o]>dp[i][o+p])
          dp[i][o+p]=dp[r][p]+dp[i][o];
       }
       int o=0;
       while(o<=leaf[r])
        {
         if(dp[r][o]>dp[i][o])
           dp[i][o]=dp[r][o];
         o++;
        }
      flag[i]=true;
     }
    if(r==0&&flag[l]) 
    {
     for(int o=leaf[i];o>=0;o--)
      for(int p=leaf[l];p>=0;p--)
       {
         if(o+p<=leaf[i]&&dp[l][p]+dp[i][o]-vert[i]>dp[i][o+p])
           dp[i][o+p]=dp[l][p]+dp[i][o]-vert[i];
       }
     int o=0;
     while(o<=leaf[l])
     {
       if(dp[l][o]-vert[i]>dp[i][o])
            dp[i][o]=dp[l][o]-vert[i];
       o++;
     }
     flag[i]=true;
   }
   if(flag[r]&&flag[l]) 
   {
     for(int o=leaf[r];o>=0;o--)
      for(int p=leaf[l];p>=0;p--)   
      {
       if(p!=0)
       {
        if(o+p<=leaf[i]&&dp[l][p]+dp[r][o]-vert[i]>dp[i][o+p])
          dp[i][o+p]=dp[l][p]+dp[r][o]-vert[i];
       }
       if(p==0)
       {
         if(dp[r][o]>dp[i][o])
           dp[i][o]=dp[r][o];
        }

     }
    flag[i]=true;
   }
  }
 }
}
   int i;
   for(i=k;i>=1;i--)
    {
       if(dp[1][i]>=0)
         break;
        }
      System.out.println(i);
    }
}