poj 1456

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define N 10010

#define inf 999999999

int pre[N];

struct node {

int x,deadline;

}map[N];

int cmp(const void *a,const void *b) {

  return (*(struct node *)b).x -(*(struct node *)a).x;

}

int find(int x) {

if(x!=pre[x])

  pre[x]=find(pre[x]);

return pre[x];

}

int main(){

int n,a,b,i,sum,max,m;

while(scanf("%d",&n)!=EOF) {

  max=-1;

  for(i=0;i<n;i++) {

   scanf("%d%d",&a,&b);

       map[i].x=a;

    map[i].deadline=b;

    max=max<b?b:max;

  }

  qsort(map,n,sizeof(map[0]),cmp);

  for(i=1;i<=max;i++)

   pre[i]=i;

  sum=0;

  for(i=0;i<n;i++) {

              m=find(map[i].deadline);

   if(m!=0) {

    sum+=map[i].x;

    pre[m]=m-1;

   }

  }

  printf("%d\n",sum);

}

return 0;

}

巴特西

poj 1456

最新文章

热门文章