题目链接
题目描述
R 君和小伙伴打算一起玩赛车。但他们被老司机 mocania 骗去了秋名山。
秋名山上有 n个点和 m条边,R 君和他的小伙伴要从点 1 出发开往点 n,每条边都有一个初始的方向。老司机 mocania 拿到了秋名山的地图但却不知道每条路有多长。显然,为了赛车游戏的公平,每条 1 到 n的路径应当是等长的。mocania 想,我就随便给边表上一个 1…9的长度,反正傻傻的 R 君也看不出来。
可 mocania 的数学不大好,不知道怎么给边标长度,只能跑来请教你这个 OI 高手了。
输入格式
第一行两个整数 n,m。
接下来 m 行,每行两个整数 u,v,表示一条从 u 到 v 的有向边。
输出格式
如果无解或者不存在 1 到 n 的路径直接输出一个 -1。
如果有解第一行输出两个数 n,m,和输入文件中给出的相同。
借下来 m 行,每行三个整数 u,v,w,表示把从 u 到 v 的路径的长度设置为 w,其中 w 是一个 1…9的整数。要求所有边的出现顺序和题目中给出的相同。
样例输入
1 | 10 10 |
样例输出
1 | 10 10 |
思路
这题其实是CF241E
给你一张有向图,你会发现从$1$到$n$的所有边必须是在$1$到$n$的必经路径上,才会影响最后的答案,于是先在正反图上各dfs一次预处理出这种边。
然后剩下的事就是给必经路径标答案了,设$dis_i$为1号点到第$i$号点的最短距离,那么对于任意边$edge=(u,v)$以得到不等式$9\geq dis_u-dis_v\geq1$拆开可得
于是很明显是差分约束的条件了。然后按我的不等式跑出来应该是最长路,非法反感判一下负环和连通性即可。
代码
写的很丑勉强看吧
下面这道是luogu的改编版,cf那道的提交记录丢这里:
http://codeforces.com/contest/241/submission/63060935
1 |
|