ccf 201503-5最小花费问题。求解_ccf吧

ccf吧关注：1,672贴子：3,244

7回复贴，共1页

ccf 201503-5最小花费问题。求解

这个题我觉得我的思路是没错的，样例也通过了，但是提交上去0分。
先说说我的思路：
根据已知的n个点，n-1条边可知，这些点和边组成的结构是树、考虑用数组保存所有的节点
定义一个结构体，结构里里边两个整型变量，一个用于保存当前节点的父节点（初始化的时候将所有节点的父节点初始化为-1，这样在加入各个边后0-n中的节点父节点值为-1的即为根节点）；另一个用于保存当前节点到父节点的距离。节点数组记为node[]。每个节点的食物售价在另外数组中保存。
对于求最小花费的起始终止点对，通过找这两个点的共同祖先节点来确定一条最短路径（树形结构下任意两点在不重复经过某点的情况下有且仅有一条路径，且这条路径是最短的）。找到共同祖先后把起点到这个祖先的高度存下记为le（left的意思）,把终点到这个祖先的高度记为ri（right的意思）。那么我们可以通过起点S0找到路径到公共祖先节点G，根据每个节点保存的父节点索引循环le+1次可以得到一串索引 S0->S1->S2->......->Sle->G;同理可以通过重点T0依次找到点T0->T1->...Tri，这个只用循环ri次，因为下个点必定是G且已经知道了它的索引（这时候吧T0...Tri从数组尾部插入到路径数组中）。完成路径保存过程中，用数组cost保存每个点食物价格，用数组road保存上个点到当前点的距离。
使用贪心算法，某个点粮食价格比前一点的贵，就在前一个点买下当前点到下一点需要的粮食（如果前一个点到当前点使用的粮食是在更前边的点买的，此处买粮食的点就是更前边的点）。
代码：len表示cost长度
for(i=0;i<len;i++){
if(cost[i+1]>cost[i])cost[i+1]=cost[i];
}
最后依次累加每两点距离即消耗粮食量*消耗粮食的单价

送TA礼物

IP属地:湖北

1楼2016-08-31 13:46回复

#include<stdio.h>
#define Num 205
typedef struct tmpnode{
int parent;
int data;
}Node,*pNode;
// 树结构
int pay[Num];
int st[Num][2];
int cost[Num],road[Num];
Node node[Num];
int main(){
int n,m,i,j,k;
int u,v,e,flag;
int le,ri,len; // le :left; ri:right 两变量分别用于后边保存开始点与结束点到他们共同祖先的深度
// len：起始到终止点路径长度=le+ri
__int64 result;
pNode p,q;
scanf("%d%d",&n,&m);
// 输入各点食物售价并初始化对应点node
for(i=0;i<n;i++){
scanf("%d",&pay[i]);
node[i].data=-1;
node[i].parent=-1;
}
// 添加边
for(i=0;i<n-1;i++){
scanf("%d%d%d",&u,&v,&e);
u--,v--; // 数组从0开始，要--
if(node[v].parent!=-1){ // 如果v的父节点已经存在那么u的父节点一定不存在，这种情况下把u视为v 的子节点
u^=v;v^=u;u^=v; //交换u v的值
}
node[v].parent = u;
node[v].data = e;
}
// 存储需要计算的起始终止点集合
for(i=0;i<m;i++){
scanf("%d%d",&st[i][0],&st[i][1]);
st[i][0]--;st[i][1]--;
}
// 对m个点分别计算 k循环变量
for(k=0;k<m;k++){
// i j分别表示起始与终止位置向上的高度从起始和终止往上一直到他们的公共点，找出路径
// 树的两点只有一条路径（在不重复经过某点情况下）
for(i=0,p=&node[st[k][0]],flag=0;;i++){
// 比较起点第i个祖先终点的所有祖先一直找到相等的那个祖先
for(j=0,q=&node[st[k][1]];;j++){
if(p==q){
flag=1;
break;
}
if(q->parent==-1)break;
q = &node[q->parent];
}
if(flag==1)break;
if(p->parent==-1)break;
p = &node[p->parent];
}
le=i;ri=j;len=i+j;
// 以下两个循环将起始到终止经过的点的粮食价格存到cost 从路径中当前点与上一点之间的距离存到road
cost[0]=pay[st[k][0]];road[0]=0;
for(i=1,p=&node[st[k][0]];i<=le;i++){
cost[i] = pay[p->parent];
road[i] = p->data;
p = &node[p->parent];
}
cost[len]=pay[st[k][1]];road[len]=node[st[k][1]].data;
for(i=len-1,p=&node[st[k][1]];i>le;i--){
cost[i] = pay[p->parent];
road[i] = node[p->parent].data;
p = &node[p->parent];
}
// 贪心
for(i=0;i<len;i++){
if(cost[i+1]>cost[i])cost[i+1]=cost[i];
}
// 累加每次经过的点所需花费最少的钱
for(result=0,i=0;i<len;i++){
result += cost[i]*road[i+1];
}
printf("%lld\n",result);
}
return 0;
}

IP属地:湖北

4楼2016-08-31 13:48

收起回复