pku 1456

2009年7月13日 星期一

题目链接：PKU 1456 Supermarket

分类：带限制的作业排序问题（贪心+并查集）

Code：

 1#include<stdio.h>
 2#include<stdlib.h>
 3#define max 10005
 4
 5int n,i,j,sum,parent[max],f[max];
 6
 7struct zuoye
 8{
 9    int p,d;
10}task[max];
11
12void init(int n)
13{
14    for(i=0;i<=n;i++)
15    {
16        parent[i]=-1;
17        f[i]=i;
18    }
19}
20int find(int x)
21{
22    if(parent[x]<0) return x;
23    else return parent[x]=find(parent[x]);
24}
25int Union(int x,int y)
26{
27    int root1=find(x),root2=find(y);
28    if(root1==root2) return root1;
29    if(parent[root1]<parent[root2])
30    {
31        parent[root1]+=parent[root2];
32        parent[root2]=root1;
33        return root1;
34    }
35    else
36    {
37        parent[root2]+=parent[root1];
38        parent[root1]=root2;
39        return root2;
40    }
41}
42void FJS()
43{
44    int i,j,l;
45    for(i=1;i<=n;i++)
46    {
47        if(task[i].d>n)j=find(n);
48        else j=find(task[i].d);
49        if(f[j]!=0)
50        {
51            sum+=task[i].p;
52            l=find(f[j]-1);
53            Union(l,j);
54            f[j]=f[l];
55        }
56    }
57    printf("%d\n",sum);
58}
59int cmp(const void *a,const void *b)
60{
61    return (*(zuoye *)b).p>(*(zuoye *)a).p? 1: -1;
62}
63int main()
64{
65    while(scanf("%d",&n)!=EOF)
66    {
67        init(n);
68        sum=0;
69        for(i=0;i<n;i++)scanf("%d %d",&task[i].p,&task[i].d);
70        qsort(task,n,sizeof(task[0]),cmp);
71        for(i=n;i>=1;i--)task[i]=task[i-1];
72        FJS();
73    }
74    return 0;
75}
76

posted on 2009-07-13 23:33 蜗牛也Coding 阅读(1000) 评论(1)  编辑 收藏 引用

评论

# re: pku 1456 2010-01-20 19:41 雪舞冰封

很受启发，这里谢过了。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜