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

我用的是拓扑排序的思想做的,在这个论坛大家给出的数据我都过了,但是就是WA,不知道怎么搞的

Posted by zczhuohuo at 2012-02-20 21:00:50 on Problem 1062
或许是对题意的理解错误吧,献上我的代码

#include <stdio.h>
#include <string.h>

#define MAX 101

int map[MAX][MAX],indegree[MAX],level[MAX],p[MAX],dequeue[MAX],result[MAX],vis[MAX];
int positive[MAX],negative[MAX];
int m,n;

int Max(int u,int v)
{
    return u<v?v:u;
}
int Min(int u,int v)
{
    return u>v?v:u;
}

void Topsort()
{
    memset(dequeue,0,sizeof(dequeue));
    memset(vis,0,sizeof(vis));
    memset(positive,0,sizeof(positive));
    memset(negative,0,sizeof(negative));
    int head=0,tail=0,i,j,u,v;
    for(i=1;i<=n;i++)
    {
        if(level[i]>level[1])
        {
            positive[i]=Max(positive[i],level[i]-level[1]);
            negative[i]=0;
        }
        else
        {
            negative[i]=Max(negative[i],level[1]-level[i]);
            positive[i]=0;
        }
        if(!indegree[i])
        {
            dequeue[tail++]=i;
            vis[i]=1;
        }
    }
    int tpositive,tnegative;
    while(tail!=head)
    {
        u=dequeue[head++];
        for(i=1;i<=n;i++)
        {
            if(map[u][i])
            {
               tpositive=positive[i];
               tnegative=negative[i];
                if(level[i]>level[1])
                {
                    positive[i]=Max(positive[u],level[i]-level[1]);
                    negative[i]=negative[u];
                }
                else
                {
                    negative[i]=Max(negative[u],level[1]-level[i]);
                    positive[i]=positive[u];
                }
                if(negative[i]+positive[i]>m)
                {
                    map[u][i]=0;
                    indegree[i]--;
                    positive[i]=tpositive;
                    negative[i]=tnegative;
                }
                else if(!vis[i])
                {
                    result[i]=Min(result[i],result[u]+map[u][i]);
                    indegree[i]--;
                }
                if(!vis[i]&&!indegree[i])
                {
                    dequeue[tail++]=i;
                    vis[i]=1;
                }
            }
        }
    }
}

int main()
{
    scanf("%d %d",&m,&n);
    int i,j,k,x,goods,bargain;
    memset(indegree,0,sizeof(indegree));
    memset(map,0,sizeof(map));
    memset(result,0,sizeof(result));
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d",&p[i],&level[i],&x);
        result[i]=p[i];
        for(j=1;j<=x;j++)
        {
            scanf("%d %d",&goods,&bargain);
            map[goods][i]=bargain;
            indegree[i]++;
        }
    }
    Topsort();
    printf("%d\n",result[1]);

    return 0;
}

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