Codeforces Round #261 (Div. 2)——Pashmak and Graph
- 题意:
n个点。m个边的有向图。每条边有一个权值,求一条最长的路径,使得路径上边值严格递增。输出路径长度
(2 ≤ n ≤ 3·105; 1 ≤ m ≤ min(n·(n - 1), 3·105)) - 分析:
由于路径上会有反复点,而边不会反复。所以最開始想的是以边为状态进行DP,get TLE……后来想想。这个问题的复杂度一直分析的不太好。对于新图。每条边仅仅訪问了一次,单单考虑这个是O(E),可是訪问时也訪问了全部点,所以是O(V+E)
考虑一下裸的DP怎样做:路径上有反复点,能够将状态具体化。dp[i][j]表示i点以j为结束边值的最长路。可是数据不同意这样。想想这个状态有一个非常大的问题,非常多状态是到达不了的,有非常多的无用状态。比方对于u->v,值为d的一条边,就须要更新dp[i][a]->dp[j][b],a<d、b>d的全部状态。
比方,假设一个权值比較大的边先更新了u->v,那么对于之后的权值比較小的边。有一部分状态就是用不到的。还有。假设真的能够用这种DP方式来解问题。在DP的时候,明显能够发现,非常多状态是能够合并的。每次更新和查询的时候都是处理一个区间,也就是说。这一个区间上的全部状态是等价的,即能够合并。看看这个合并有什么特点:对于确定的一条边(u->v,
d)对于u的状态中,小于d的是能够合并的,还有一个角度看。也就是说。对于确定的边,仅仅有全部的j < d的状态才是有可能转移的状态。那么考虑一下,假设我们将边先排好序,那么在每一条边增加的时候,全部的状态都是有效状态了,既然都是有效状态(即都是有可能进行转移的),那么事实上就不是必需记录第二维状态了。DP[i]表示处理到当前边之前,以i结束的最长路径长度。至此,问题可解。既然是排序解决,必定要处理的就是两个值同样的情况,两个数组就可以。
当前问题(问题A)对照一下这个问题(问题B),有一些相似性:问题B的路径也是须要递增的(假设将一条合法路径上的全部開始时间和关闭时间按顺序写下来),可是和A一比就有一个明显的特点。一个边有两个值。相同的先考虑二维DP。有效状态也是比当前边的起始状态小的。可是更新之后的状态的值就不一定了,由于更新的状态的值是当前边的第二个属性,所以对于(1,
5)、(2, 6),就没有一个明显的先后影响顺序了。而问题A的有效状态和B一样。可是更新后的状态的值必定都是边值(排序之后,对于之后的边也是有效的)。这样考虑。B问题用DP解决就有点没有思路了,可是。再和A比較后发现。B给了一个条件:起点是确定的;而A是不定起点。既然求得是确定起点的路径,那么就能够往最短路上想想。
题目要求的是时间最短。那么就能够把时间看作距离来最短路就可以。
const int MAXN = 1100000; int dp[MAXN], f[MAXN]; struct Edge
{
int u, v, d;
bool operator< (const Edge& rhs) const
{
return d < rhs.d;
}
} ipt[MAXN]; int main()
{
int n, m;
while (~RII(n, m))
{
CLR(dp, 0); REP(i, m)
RIII(ipt[i].u, ipt[i].v, ipt[i].d);
sort(ipt, ipt + m);
REP(i, m)
{
int nxt = i;
while (nxt + 1 < m && ipt[i].d == ipt[nxt + 1].d)
nxt++;
FE(j, i, nxt)
{
int u = ipt[j].u, v = ipt[j].v;
f[v] = max(f[v], dp[u] + 1);
}
FE(j, i, nxt)
{
int v = ipt[j].v;
dp[v] = f[v];
}
i = nxt;
}
int ans = 0;
FE(i, 1, n)
ans = max(ans, dp[i]);
WI(ans);
}
return 0;
}
最新文章
- [转载]跨域iframe高度自适应
- SSAS动态添加分区(一)
- Atom编辑器在windows下怎么更改安装路径
- css知多少(5)——选择器
- 【java】:解析xml
- 【BZOJ】1038: [ZJOI2008]瞭望塔
- OpenSSL重大漏洞-Heartbleed之漏洞利用脚本POC讲解
- JW Player 现在支持 Azure 媒体服务
- C++ 直方图匹配算法代码
- redmine 出口中国的乱码
- 洛谷 P2622 关灯问题II【状压DP;隐式图搜索】
- selenium获取元素后用click()点击没有作用,用Keys.ENTER就可以成功
- windows 时间服务器配置详解
- python属性管理(1):基础
- 把ResNet-L152模型的ckpt文件转化为pb文件
- 从零开始搭建自己的VueJS2.0+ElementUI单页面网站(一、环境搭建)
- oracle 监听文件 说明
- WebGL模型拾取——射线法二
- 将JDBC的resultSet映射到JavaBaen
- 倒计时 总结 Timer Handler CountDownTimer RxJava MD