程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [hdu 4274]Spy&#39;s Work 樹形dp

[hdu 4274]Spy&#39;s Work 樹形dp

編輯：C++入門知識

[hdu 4274]Spy's Work 樹形dp

Spy's Work

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1266 Accepted Submission(s): 388

Problem Description I'm a manager of a large trading company, called ACM, and responsible for the market research. Recently, another trading company, called ICPC, is set up suddenly. It's obvious that we are the competitor to each other now!
To get some information about ICPC, I have learned a lot about it. ICPC has N staffs now (numbered from 1 to N, and boss is 1), and anybody has at most one superior. To increase the efficiency of the whole company, the company contains N departments and the ith department is led by the ith staff. All subordinates of the ith staff are also belong to the ith department.
Last week, we hire a spy stealing into ICPC to get some information about salaries of staffs. Not getting the detail about each one, the spy only gets some information about some departments: the sum of the salaries of staff s working for the ith department is less than (more than or equal to) w. Although the some inaccurate information, we can also get some important intelligence from it.
Now I only concerned about whether the spy is telling a lie to us, that is to say, there will be some conflicts in the information. So I invite you, the talented programmer, to help me check the correction of the information. Pay attention, my dear friend, each staff of ICPC will always get a salary even if it just 1 dollar!

Input There are multiple test cases.
The first line is an integer N. (1 <= N <= 10,000)
Each line i from 2 to N lines contains an integer x indicating the xth staff is the ith staff's superior(x The next line contains an integer M indicating the number of information from spy. (1 <= M <= 10,000)
The next M lines have the form like (x < (> or =) w), indicating the sum of the xth department is less than(more than or equal to) w (1 <= w <=100,000,000)

Output For each test case, output "True" if the information has no confliction; otherwise output "Lie".

Sample Input

Sample Output

Lie
True

Source 2012 ACM/ICPC Asia Regional Changchun Online

題目大意

一個公司是一個樹狀結構（每個人有一個直接上司，1號員工是主管）

現在已知m條信息，每條信息的格式是該員工及其下屬所得薪資總合大於小於或等於某個值，問這些信息是否相互矛盾

解題思路

樹狀dp 每個節點記錄最大值與最小值，dfs處理每個點，每個點的min更新為其下屬的min之和 +1(至少有一元薪水)

並判斷max是否

dp確實范圍比較廣了，還是要對圖論的一些內容有些認識

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define sqr(x) ((x)*(x))
#define LL long long 
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define eps 1e-10
#define maxn 10007
using namespace std;
int nex[maxn+5],u[maxn+5],v[maxn+5];
LL maxx[maxn+5],minn[maxn+5];
int en;
int fir[maxn+5];
int n,m,num,number,flag;
char relative;
void addedge(int x,int y)
{
  en++;
  u[en]=x;
  v[en]=y;
  nex[en]=fir[u[en]];
  fir[u[en]]=en;
}
void dfs(int x)
{
  LL mi=1;
  for (int e=fir[x];~e;e=nex[e])
  {
    dfs(v[e]);
    mi+=minn[v[e]];
  }
  minn[x]=max(mi,minn[x]);
  if (maxx[x]') minn[num]=max(minn[num],(LL)number+1);
      if (relative=='=') {
        maxx[num]=min(maxx[num],(LL)number);
        minn[num]=max(minn[num],(LL)number);
      }
    }
    dfs(1);
    if (flag) puts("Lie");
    else puts("True");
  }
  return 0;
}