清华大学历年考研复试机试真题 -图
发布时间
阅读量：
阅读量
问题概述
包含 q 次查询，在每一次查询中都涉及两个参数 u 和 c 的设定
每当一个点被反复穿过时，在这种情况下它的价值应当被累加起来计数。除了上述情况外，在起点节点的价值也同样需要计入
输入输出格式
输入描述:
从标准输入读入数据。
输入的第一行包含三个由空格隔开的正整数 n,m,q，保证 N≤2,000 和 M≤8,000,Q≤10^5。
下一行将包含n个以空格分隔的非负整数值vi，并代表编号从小到大的所有点的价值，并满足vi≤10^4的条件
以下将列出m个由空格分隔的三元组(x, y, z)，满足条件：对于每个三元组中的x和y都满足1 ≤ x, y ≤ n，并且z满足1 ≤ z ≤ 30。每个三元组表示从顶点x到顶点y的一条有向边其权重为z
q 组数据每个条目由两个非负整数组成，并以空格分隔。这些整数满足 1≤u≤n 和 0≤c≤800 的条件。
将结果发送至标准输出端口。
每当进行一次查询时，请计算并输出对应的数值
输入与输出示例如下：
输入与以下参数组合：
例如：
9个节点6条边
节点之间的连接权重如下：
节点之间的距离设置如下：
运行算法所得的结果包括以下内容：
其中每个结果对应特定查询条件下的最优路径总价值
算法实现的具体步骤包括以下几点：
直接DFS遍历
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define vMAX 2000
int mp[vMAX+1][vMAX+1]; //存储边权 即成本
int v[vMAX+1]; //存储顶点 即价值
int max; //每轮计算结果
void DFS(int beg,int c,int n,int value); //深度遍历 beg为当前起始顶点 c为剩余成本 value为当前价值总和
int main(){
memset(mp,INF,sizeof(mp)); //初始化 及 输入数据
int n,m,q,c,beg,i,a,b,t;
scanf("%d %d %d",&n,&m,&q);
for(i=1;i<=n;i++) scanf("%d",&v[i]);
for(i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&t);
mp[a][b]=t;;
}
for(i=0;i<q;i++){
scanf("%d %d",&beg,&c);
max=0;
DFS(beg,c,n,v[beg]); //开始遍历
printf("%d\n",max);
}
return 0;
}
void DFS(int beg,int c,int n,int value){
int i;
if(value>max) max=value; //每次先判断是否当前价值超过最大值了
for(i=1;i<=n;i++){
if(mp[beg][i]<=c) DFS(i,c-mp[beg][i],n,value+v[i]); //只要边成本能接受 就深入试试
}
}另一种错误方法 贪心
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define vMAX 2000
typedef struct side{
double roc;
int cost;
}side;
side mp[vMAX+1][vMAX+1];
int v[vMAX+1];
int MAX(int beg,int c,int n);
int main(){
memset(mp,INF,sizeof(mp));
int n,m,q,c,beg,next,i,j,a,b,t,value;
scanf("%d %d %d",&n,&m,&q);
for(i=1;i<=n;i++) scanf("%d",&v[i]);
for(i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&t);
mp[a][b].cost=t;
mp[a][b].roc=1.0*v[b]/t;
}
//贪心 但此处局部最优 并不能构成全局最优 所以不对
for(i=0;i<q;i++){
scanf("%d %d",&beg,&c);
value=v[beg];
next=0;
while(next>=0){
next=MAX(beg,c,n);
c-=mp[beg][next].cost;
value+=v[next];
beg=next;
}
printf("%d\n",value);
}
return 0;
}
int MAX(int beg,int c,int n){
int i,next=-1;
double max=0;
for(i=1;i<=n;i++){
if(i!=beg && mp[beg][i].cost<=c && mp[beg][i].roc>max){
max=mp[beg][i].roc;
next=i;
}
}
return next;
}全部评论 (0)
还没有任何评论哟~