 /**//*
題意:給出一棵n個結點的樹,兩個人一起走,輪流決策 Alice目的是使最后距離最小 Bob相反
問最終走的距離能否滿足區間[L,R]
(需要走到最后不能走,所以Alice不能不選就結束了)
如果沒有[L,R],直解dfs,Bob的話選最大兒子走,Alice選最小兒子走
現在多了[L,R],選的時候,就需要判斷滿足總距離(是總距離!!即答案)滿足[L,R]然后再選最大/小
在結點u判斷選擇是否滿足條件時,需要多記錄一個dist[u]表示從根0到u的距離
if(dist[u] + dp[v] + w <= R && dist[u] + dp[v] + w >= L)
才更新答案
啟示:知道某個節點,就知道了根0到它的距離以及輪到誰決策
這是很有用的性質,最終答案就是 dist[u]+dp[v]+w
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int MAXN = 500010;
const int INF = 1000010000;

struct Node
  {
int v,w;
Node *next;
};

Node nodes[MAXN],*E[MAXN],*pE;
int N,L,R;
int dp[MAXN],dist[MAXN];

void init()
  {
for(int i=0;i<N;i++)
E[i] = NULL;
pE = nodes;
}

void add(int u,int v,int w)
  {
pE->v = v;
pE->w = w;
pE->next = E[u];
E[u] = pE++;
}

void dfs(int u,bool who)//true for Bob false for Alice
  {
 if(dist[u]>R) {dp[u] = 0;return;}
int &ans = dp[u];
ans = who?0:INF;
if(E[u] == NULL)ans = 0;
for(Node *it = E[u];it;it=it->next)
 {
int v = it->v, w = it->w;
dist[v] = dist[u] + w;
dfs(v,!who);
if(dist[u] + dp[v] + w <= R && dist[u] + dp[v] + w >= L)
 {
if(who)ans = max(ans,dp[v]+w);
else ans = min(ans,dp[v]+w);
}
}
// if(ans>R) ans = R+10;
}

int main()
  {
freopen("in","r",stdin);
int a,b,c;
while(~scanf("%d%d%d",&N,&L,&R))
 {
init();
for(int i=1;i<N;i++)
 {
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dfs(0,1);
if(dp[0]<=R && dp[0]>=L)printf("%d\n",dp[0]);
else puts("Oh, my god!");
}
return 0;
}
|
這題G++會超時 C++可以過
感覺Hdu卡常數了
O(n)的算法
7 2 8
0 1 1
0 2 1
1 3 1
1 4 10
2 5 1
2 6 5
7 4 8
0 1 1
0 2 1
1 3 1
1 4 2
2 5 1
2 6 5
4 2 6
0 1 1
1 2 1
1 3 5
運行出來答案不對啊.
多謝指出
是兩條語句的順序問題
改為這樣
dist[v] = dist[u] + w;
dfs(v,!who);
就可以了吧?
1.dp[v]代表什么?為什么dp[0]是最后的答案?
2.您的做法是樹形DP嗎?還是貪心?
恩,是樹形dp
dp[v]表示以v為根的子樹獲得的最優值
由于有L,R
這個值需要 L<=dist[v]+dp[v]<=R即在決策時找一些合法的點來更新u)
dist[0]=0,那么dp[0]就是答案了
哦~這樣的話,是不是一定要走到葉子結點才行?
我那個dfs里有加一句
if(dist[u]>R){dp[u] = 0;return;}
如果還沒到葉子就已經不行了就不走了
如果一直都滿足條件的話就會走到葉子了
回復的真快。。我明白了~謝了~
不客氣
如果只有Bob選過一條路,雖然沒到葉子節點,但是如果再選就會>R
這樣要輸出"Oh, my god!"?
ps:數據為:
7 5 10
0 1 2
0 2 3
1 3 30
1 4 40
2 5 50
2 6 60
能幫我看看嘛?
#include <iostream>
#include <fstream>
//#include <cmath>
//#include <algorithm>
#include <cstring>
//#include <stack>
using namespace std;
ifstream fin("test.in");
#define cin fin
struct node
{
struct node *next;
int num;
int value;
node()
{
next=NULL;
num=-1;
value=0;
}
};
typedef struct node NODE;
typedef struct node* PNODE;
int n,L,R,from,to,dis;
const long long MM=2000000000;
NODE list[500100];
void insert(int fa,int fb,int val)
{
PNODE p=&list[fa];
while(p->next)
{
p=p->next;
}
p->next=new NODE;
p->next->value=val;
p->next->num=fb;
}
void del(int fa)
{
if(list[fa].next==NULL)
return;
PNODE p=list[fa].next,tempp;
list[fa].next=NULL;
while(p->next)
{
tempp=p;
p=p->next;
delete tempp;
}
delete p;
}
int dfs(int s,int deep)
{
if(deep%2==0)
{
PNODE p=list[s].next;
if(p==NULL)
return 0;
else
{
int tempnum=0,ftt;
while(p)
{
ftt=p->value+dfs(p->num,deep+1);
if(ftt>tempnum)
tempnum=ftt;
p=p->next;
}
return tempnum;
}
}
else
{
PNODE p=list[s].next;
if(p==NULL)
return 0;
else
{
int tempnum=MM,ftt;
while(p)
{
ftt=p->value+dfs(p->num,deep+1);
if(ftt<tempnum)
tempnum=ftt;
p=p->next;
}
return tempnum;
}
}
}
int main()
{
while(~scanf("%d%d%d",&n,&L,&R))
{
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&from,&to,&dis);
insert(from,to,dis);
}
int ans=dfs(0,0);
if(ans<=R&&ans>=L)
{
cout << ans << endl;
}
else
cout << "Oh, my god!" << endl;
for(int i=0;i<n;i++)
del(i);
}
return 0;
}
是丫