[USACO2010 Mar Gold 【gather】]树形dp

【题目链接】http://ace.delos.com/ioiupload?init=1&a=uNRSh9JKRlk
【题目大意】
就是给一颗树,树上的点都有不同数目的奶牛。
然后边有边权。
让你选一个结点,使得所有牛到这个点走的路程之和最小。
【算法分析】
随便拿个点做根。
两次DFS。
第一次算出两个信息:
1、以该结点为根的子树上的牛的总数目。
2、该结点的子孙到该点的距离之和。
第二次算出另一个信息:
从父亲来的那部分需要的距离之和。
最后将两部分相加即可。
【其它】1Y。
【CODE】
/*
ID:jie22221
TASK:gather
LANG:C++
*/
#include #include #include #include using namespace std;
typedef long long lld;
const int N=105555;
struct edge{int x,y,w;edge *next;}*ls[N];
int n;
int c[N];
lld f[N],cow[N],From_Fa[N],ans=(lld)(1) << 60; void addedge(int x,int y,int w){
edge *t=(edge *)malloc(sizeof(edge));
t->x=x; t->y=y; t->w=w; t->next=ls[x]; ls[x]=t;
}

void init(){
ios::sync_with_stdio(false);
cin >> n;
for (int i=1;i<=n;i++) cin >> c[i];
for (int i=1,x,y,w;i cin >> x >> y >> w;
addedge(x,y,w);
addedge(y,x,w);
}
}

void predfs(int p,int fa){
cow[p]=c[p];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
predfs(t->y,p);
f[p]+=cow[t->y]*t->w+f[t->y];
cow[p]+=cow[t->y];
}
}

void dfs(int p,int fa){
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
From_Fa[t->y]=From_Fa[p]+f[p]-f[t->y]-cow[t->y]*t->w+(cow[1]-cow[t->y])*t->w;
dfs(t->y,p);
}
ans=min(ans,From_Fa[p]+f[p]);
}

int main(){
freopen("gather.in","r",stdin);
freopen("gather.out","w",stdout);
init();
predfs(1,0);
dfs(1,0);
cout << ans << endl;
return 0;
}

加入对话

10条评论

  1. 回复ad饕饕不绝:应该的,因为你搞next的时候,要用到一个类似t=g[t].next的东东。然后g[t]这里这个调用是要用时间的。但是一般也不差多少。。。估计是其它地方吧。。。

  2. 回复Apocalypse9:这个。。。USACO的数据好像没有链的,应该没事。而且oimaster神牛做过测试,G++编译的,在windows下能开500000的int数组。FPC2.0.4能开好像几万。而FPC2.2.4能开4000000的longint。然后这题只有100000的话,可能爆可能不爆。。= =在边沿吧。

留下评论

回复 ad饕饕不绝 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注