| ||||||||||
| 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