[BZOJ1663] [Usaco2006 Open]赶集（spfa最长路）

传送门

按照时间t排序

如果 t[i] + map[i][j] <= t[j]，就在i和j之间连一条边

然后spfa找最长路

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 401

using namespace std;

int n, ans, cnt;

int a[N][N], map[N][N], dis[N], head[N], to[N * 100], next[N * 100];

bool vis[N];

queue <int> q;

struct node

{

	int t, id;

}p[N];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline bool cmp(node x, node y)

{

	return x.t < y.t;

}

inline void spfa()

{

	int i, u, v;

	q.push(0);

	while(!q.empty())

	{

		u = q.front();

		q.pop();

		vis[u] = 0;

		for(i = head[u]; ~i; i = next[i])

		{

			v = to[i];

			if(dis[v] < dis[u] + 1)

			{

				dis[v] = dis[u] + 1;

				if(!vis[v])

				{

					q.push(v);

					vis[v] = 1;

				}

			}

		}

	}

}

inline void add(int x, int y)

{

	to[cnt] = y;

	next[cnt] = head[x];

	head[x] = cnt++;

}

int main()

{

	int i, j, k;

	n = read();

	memset(head, -1, sizeof(head));

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

		p[i].id = i, p[i].t = read();

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

		for(j = 1; j <= n; j++)

			map[i][j] = read();

	sort(p + 1, p + n + 1, cmp);

	for(i = 1; i <= n; i++) map[0][i] = map[1][i];

	p[0].id = p[0].t = 0;

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

		for(j = i + 1; j <= n; j++)

			if(p[i].t + map[p[i].id][p[j].id] <= p[j].t)

				add(p[i].id, p[j].id);

	spfa();

	for(i = 1; i <= n; i++) ans = max(ans, dis[i]);

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

	return 0;

}