link:http://acm.hdu.edu.cn/showproblem.php?pid=2647

这题起初看没有什么难度,直接建表,然后进行减度比较钱数即可,对于

输出-1的情况实际就是判断是否存在环。。但下笔之后发现,题中n的范围是10000,如果

用数组的话肯定会超,所以就想到了换用链表去实现,想到这个问题也就好解决了。。

代码比较拙劣,仅供参考~~~

code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 10010
struct node
{
    int k;
    struct node *next;
}*map;
int *degree,*money,n;
int maxx(int x,int y)
{
    return x>y?x:y;
}
void init()
{
    int i;
    degree=(int *)malloc(sizeof(int)*(n+1));
    money=(int *)malloc(sizeof(int)*(n+1));
    map=(struct node *)malloc(sizeof(struct node)*(n+1));
    for(i=1;i<=n;i++)
    {
        map[i].k=0;
        map[i].next=NULL;
        money[i]=888;
        degree[i]=0;
    }
}
void add(int x,int y)
{
    struct node *p;
    p=(struct node *)malloc(sizeof(struct node));
    degree[x]++;
    p->k=x;
    p->next=map[y].next;
    map[y].next=p;
}
int Topsort()
{
    int i,j;
    struct node *p;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(degree[j]==0)
            {
                degree[j]=-1;
                break;
            }
        }
        if(j>n)
            return 0;
        p=map[j].next;
        while(p)
        {
            degree[p->k]–;
            money[p->k]=maxx(money[p->k],money[j]+1);
            p=p->next;
        }
    }
    return 1;
}
int main()
{
    int m,x,y,flag;
    while(scanf(“%d%d”,&n,&m)!=EOF)
    {
        init();
        while(m–)
        {
            scanf(“%d%d”,&x,&y);
            add(x,y);
        }
        flag=Topsort();
        if(flag)
        {
            for(m=2;m<=n;m++)
                money[1]+=money[m];
            printf(“%d\n”,money[1]);
        }
        else
        {
            printf(“-1\n”);
        }
        free(degree);
        free(money);
        free(map);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation