| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
请教一下大神,这叫什么算法?#include<stdio.h>
#include<string.h>
#define num 103
#define big 9999999
double maxcost[num];
int visit[num];
int n,m,s;
double v;
double rate[num][num],yj[num][num];
void fun()
{
int max,i,j,tmp;
double tmp_cost;
memset(visit,0,sizeof(visit));
memset(maxcost,0,sizeof(maxcost));
maxcost[s]=v;
while(1)
{
for(j=1;j<=n;j++)
if(visit[j]==0&&maxcost[j]!=0)
{
tmp=j;
break;
}
if(j==n+1)
{
printf("NO\n");
return ;
}
visit[tmp]=1;
for(j=1;j<=n;j++)
{
if(rate[tmp][j]!=0)
{
tmp_cost=(maxcost[tmp]-yj[tmp][j])*rate[tmp][j];
if(tmp_cost>maxcost[j])
{
if(j==s)
{
printf("YES\n");
return ;
}
maxcost[j]=tmp_cost;
visit[j]=0;
}
}
}
}
printf("NO\n");
}
int main()
{
freopen("input.txt","r",stdin);
int i,j,p1,p2;
scanf("%d%d%d%lf",&n,&m,&s,&v);
memset(rate,0,sizeof(rate));
while(m--)
{
scanf("%d%d",&p1,&p2);
scanf("%lf%lf%lf%lf",&rate[p1][p2],&yj[p1][p2],&rate[p2][p1],&yj[p2][p1]);
}
fun();
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator