【拓扑+DP】HDU 4109 Instrction Arrangement

KIDx的解题报告

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4109

题意：输入点数n[编号0到n-1]和关系数，输入a，b，c，表示a操作做完后第c纳秒可以做b，问所有操作搞完至少花多长时间？

 

Sample Input

5 2
1 2 1
3 4 1

 

Sample Output

2

Hint
In the 1st ns, instruction 0, 1 and 3 are executed;
In the 2nd ns, instruction 2 and 4 are executed.
So the answer should be 2.

 

 

 

间DP思路：dp[v] = max (dp[v], dp[ui]+w[ui][v])，ui指v的第i个父结点，就是所有父结点转移过来咯，为什么是max？因为要搞完所有父结点才能搞自己嘛

#include <iostream>
#include <queue>
using namespace std;
#define M 1005
#define max(a,b) (a>b?a:b)

struct edge{
	int v, w, nxt;
}e[10005];

int p[M], cnt, n, ind[M], dp[M];

void init ()
{
	cnt = 0;
	memset (p, -1, sizeof(p));
	memset (ind, 0, sizeof(ind));
}

void addedge (int u, int v, int w)
{
	e[cnt].v = v, e[cnt].w = w, e[cnt].nxt = p[u], p[u] = cnt++;
}

int main()
{
	int m, u, v, w, i;
	while (~scanf ("%d%d", &n, &m))
	{
		init ();
		while (m--)
		{
			scanf ("%d%d%d", &u, &v, &w);
			addedge (u, v, w);
			ind[v]++;
		}
		queue<int> q;
		for (i = 0; i < n; i++)
		{
			if (ind[i] == 0)
				q.push (i), dp[i] = 1;
			else dp[i] = 0;
		}
		while (!q.empty())
		{
			u = q.front();
			q.pop();
			for (i = p[u]; i != -1; i = e[i].nxt)
			{
				v = e[i].v;
				w = e[i].w;
				dp[v] = max (dp[v], dp[u]+w);
				if (--ind[v] == 0)
					q.push (v);
			}
		}
		int ans = 0;
		for (i = 0; i < n; i++)
			if (ans < dp[i])
				ans = dp[i];
		printf ("%d\n", ans);
	}
	return 0;
}