Hdu 4109 Instruction Arangement

大意は改めて述べるまでもない.
考え方:典型的なキーポイントパスは、データ構造書に紹介されています.注意すべきのは、イベントの最小開始時間です.ここの番号は活動0から始まります.だから、0より0までの開始時間は1で、初期化の時に注意すればいいです.

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 1010;
const int MAXM = 10010;

struct Edge
{
	int v, w;
	int id;
	int next;
}edge[MAXM];

int n, m;
int cnt;

int first[MAXN];
int ind[MAXN], outd[MAXN];
int Ee[MAXN], El[MAXN], E[MAXN], L[MAXN];
/*  Ee      ，  El        ，E  a      ，L  a        */
void init()
{
	cnt = 0;
	memset(first, -1, sizeof(first));
	memset(ind, 0, sizeof(ind));
	memset(outd, 0, sizeof(outd));
	memset(Ee, 0, sizeof(Ee));
}

void read_graph(int u, int v, int w)
{
	edge[cnt].v = v, edge[cnt].w = w;
	edge[cnt].next = first[u], first[u] = cnt++;
}

void toposort()
{
	queue<int> q;
	for(int i = 0; i < n; i++) if(!ind[i])
	{
		q.push(i);
		Ee[i] = 1;
	}
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v, w = edge[e].w;
			if(--ind[v] == 0) q.push(v);
			if(Ee[v] < Ee[x] + w)
			{
				Ee[v] = Ee[x] + w;
			}
		}
	}
}

void read_case()
{
	init();
	while(m--)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		read_graph(u, v, w);
		ind[v]++;
	}
}

void solve()
{
	int ans = 0;
	read_case();
	toposort();
	for(int i = 0; i < n; i++) ans = max(ans, Ee[i]); //        。 
	printf("%d
", ans);
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		solve();
	}
	return 0;
}