Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

请教一下大神,这叫什么算法?

Posted by 2012xie at 2013-02-17 16:07:26 on Problem 1860
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator