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;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
动态规划DP题解 POJ HDU部分动态规划DP题解
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu 1005.比较简单的一道题,有兴趣的可以看看。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 1695 GCD(欧拉函数+容斥原理).docx
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧