Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我用的是拓扑排序的思想做的,在这个论坛大家给出的数据我都过了,但是就是WA,不知道怎么搞的或许是对题意的理解错误吧,献上我的代码 #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator