2332354_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#define INIT (Edge *)malloc(sizeof(Edge))

long ans;
int l, n, b;
int C[1001][1001];
long F[1001][1001];
typedef struct node
{
	int adj;
	struct node *next;
}Edge;

struct Node
{
	Edge *head;
}adj[1001];

void dfs(int v,int c,long f)
{
	Edge *s;

	if(c>b)
		return ;
	if(v==l&&f>ans)
	{
		ans = f;
		return ;
	}
	s = adj[v].head;
	while(s->next)
	{
		dfs(s->next->adj,c+C[v][s->next->adj],f+F[v][s->next->adj]);
		s = s->next;
	}
}

int main()
{
	int i;
	Edge *s;
	int x, w, c; 
	long f;

	scanf("%d%d%d",&l,&n,&b);
	for(i = 0; i <= l; i++)
	{
		adj[i].head = INIT;
		adj[i].head->next = NULL;
	}
	for(i = 0; i < n; i++)
	{
		scanf("%d%d%d%d",&x,&w,&f,&c);
		if(C[x][x+w])
		{
			if(f*C[x][x+w]>c*F[x][x+w])
			{
				C[x][x+w] = c;
				F[x][x+w] = f;
			}
			continue;
		}
		s = INIT;
		s->adj = x+w;
		s->next = adj[x].head->next;
		adj[x].head->next = s;
		F[x][x+w] = f;C[x][x+w] = c;
	}
	ans = -1;
	dfs(0,0,0);
	printf("%ld\n",ans);
	return 1;
}