为啥要给这个水题写个解题报告呢
因为这个题太坑人了。
非常简单的题意,但是数据量超级大
我首先用了DFS,毫无疑问超时了
然后又BFS,居然又超时了
然后加上超级源点超级汇点后SPFA,各种WA后继续超时
最后逼急了去写拓扑排序,瞬间就过了。 加了读入优化后能排进第一版了。
其实刚开始就准备写拓扑了,但是为了试验算法,TLE和WA了好长时间,
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
#define MAXM 1200005
#define INF 2100000000
using namespace std;
int e, n, m;
int head[MAXN], val[MAXN];
int dp[MAXN], q[MAXN];
int ind[MAXN], outd[MAXN];
struct Edge
{
int v, next;
}edge[MAXM];
void insert(int x, int y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
memset(ind, 0, sizeof(ind));
memset(outd, 0, sizeof(outd));
}
void topsort()
{
int h = 0, t = 0;
for(int i = 1; i <= n; i++)
if(ind[i] == 0) q[t++] = i;
while(h < t)
{
int u = q[h++];
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
dp[v] = max(dp[v], dp[u] + val[v]);
ind[v]--;
if(ind[v] == 0) q[t++] = v;
}
}
}
int main()
{
int x, y;
while(scanf("%d%d", &n, &m) != EOF)
{
init();
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
while(m--)
{
scanf("%d%d", &x, &y);
insert(x, y);
ind[y]++;
outd[x]++;
}
for(int i = 1; i <= n; i++) dp[i] = -INF;
for(int i = 1; i <= n; i++)
if(ind[i] == 0) dp[i] = val[i];
topsort();
int ans = -INF;
for(int i = 1; i <= n; i++)
if(outd[i] == 0) ans = max(ans, dp[i]);
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://200830740306.iteye.com/blog/603488
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
北大POJ初级-简单搜索 解题报告+AC代码
poj 1091 拓扑排序加上foyld_warshall算法实现
西北工业大学POJ试题C++答案代码+课程设计
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1159-Palindrome 解题报告+AC代码