nyoj 307

/*这是一道最短路变形题

从每个有藏宝的地方为起点求到各个点的可以的最大重量，相当于求出了从出口到一个藏宝点所

允许的最大重量，把所有藏宝点的按重量排序（从小到大）先到最小的藏宝点带上宝物再去次大

*/

#include<stdio.h>

#include<stdlib.h>

#include<queue>

#include<string.h>

using namespace std;

const int N =16000;

struct node {

int u,v,w,next;

}bian[N*2];

int head[8100],yong,n;

void addedge(int u,int v,int w) {//建邻接表

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];//bian[yong].next用来记录上一个边的index

head[u]=yong++;//head[u]代表当前边的index

}

int Min(int a,int b) {

return a>b?b:a;

}

int cmp(const void *a,const void *b) {//排序

return *(int *)a-*(int *)b;

}

int maxvalue_start(int start) {//相当于当前点到1可以通过的最大宝物

int visit[8100],dis[8100];

int i;

memset(dis,0,sizeof(dis));//用来储存从start开始所能得到的最大宝物数目

memset(visit,0,sizeof(visit));//标记

visit[start]=1;

dis[start]=1000000000;

while(start!=1){//如果1这个点就是从start开始的可以得到的最大宝物就结束while循环

for(i=head[start];i!=-1;i=bian[i].next) {

int v=bian[i].v;

int w=bian[i].w;

if(!visit[v]&&dis[v]<Min(dis[start],w))//求所有与当前点相连的点可以得到的最大宝物

dis[v]=Min(dis[start],w);

}

int mmax=0;

for(i=1;i<=n;i++)

if(!visit[i]&&mmax<dis[i]) {//从最大的可以通过的宝物开始遍历相连的边

mmax=dis[i];

start=i;

}

visit[start]=1;

}

return dis[1];//返回最大宝物数

}

int main() {

int m,j,w,i,k,t,maxv[8100],total,loc[8100];

while(scanf("%d%d%d%d",&n,&m,&k,&w)!=EOF) {

memset(head,-1,sizeof(head));

yong=0;

for(i=0;i<k;i++)

scanf("%d",&loc[i]);

while(m--) {

scanf("%d%d%d",&i,&j,&t);

addedge(i,j,t);//加双向边

addedge(j,i,t);//

}

for(i=0;i<k;i++)

maxv[i]=maxvalue_start(loc[i]);//求每个有宝物的点到出口能够拿到的最大宝藏数目

qsort(maxv,k,sizeof(maxv[0]),cmp);//排序

total=0;

for(i=0;i<k;i++)//先到最小的藏宝点带上宝物再去次大

if(maxv[i]>=(total+1)*w)

total++;

printf("%d\n",total);

}

return 0;

}

巴特西

nyoj 307

最新文章

热门文章