qnickx's blog

循此苦旅,直抵群星


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 搜索

P5590&&CF241E 赛车游戏 题解

发表于 2019-10-22 分类于 OI , 题解 阅读次数:

题目链接

传送门

题目描述

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
2
3
4
5
6
7
8
9
10
11
10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10

样例输出

1
2
3
4
5
6
7
8
9
10
11
10 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 10 9

思路

这题其实是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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <climits>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1005,maxm=5005;
int n,m,tot,lxt[maxm<<1],head[maxn],ver[maxm<<1],Nxt[maxm<<1],head_2[maxn],ver_2[maxm<<1],Nxt_2[maxm<<1],edge_2[maxm<<1],tot_2;
int dis[maxn],ok[maxn];
bool inq[maxn],flag,pd[maxn],vis[maxn];
queue<int> q;
inline void add1(int u,int v){
ver[++tot]=v,Nxt[tot]=head[u],lxt[tot]=u,head[u]=tot;
}
int tot_3,head_3[maxm<<1],ver_3[maxm<<1],Nxt_3[maxm<<1];
inline void add3(int u,int v){
ver_3[++tot_3]=v,Nxt_3[tot_3]=head_3[u],head_3[u]=tot_3;
}
inline void add_2(int u,int v,int l){
ver_2[++tot_2]=v,edge_2[tot_2]=l,Nxt_2[tot_2]=head_2[u],head_2[u]=tot_2;
}

inline void dfs1(int u){vis[u]=true;for(register int i=head[u];i;i=Nxt[i]){if(vis[ver[i]]) continue;dfs1(ver[i]); }}
inline void dfs2(int u){pd[u]=true;for(register int i=head_3[u];i;i=Nxt_3[i]){if(pd[ver_3[i]]) continue;dfs2(ver_3[i]); }}

inline void spfa(){
for(register int i=1;i<=n;i++) dis[i]=-999999999;
q.push(1);
inq[1]=true,dis[1]=0,ok[1]=1;
while(!q.empty()){
int u=q.front();q.pop();
// printf("spfa:%d\n",u);
inq[u]=false;
for(register int i=head_2[u];i;i=Nxt_2[i]){
int v=ver_2[i];
if(dis[v]<dis[u]+edge_2[i]){
dis[v]=dis[u]+edge_2[i];
// printf("test1\n");
if(inq[v]) continue;
// printf("test2\n");
ok[v]++,inq[v]=true,q.push(v);
if(ok[v]>n){flag=true;return;}
}
}
}
}

int main(){
//freopen("test.txt","r",stdin);
scanf("%d%d",&n,&m);
for(register int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),add1(u,v),add3(v,u);
dfs1(1),dfs2(n);
if(!pd[1]||!vis[n]){printf("-1");return 0;}
for(register int i=1;i<=m;i++) if(vis[lxt[i]]&&pd[lxt[i]]&&vis[ver[i]]&&pd[ver[i]]) add_2(lxt[i],ver[i],1),add_2(ver[i],lxt[i],-9);
spfa();
if(flag){printf("-1");return 0;}
printf("%d %d\n",n,m);
for(register int i=1;i<=m;i++){
printf("%d %d ",lxt[i],ver[i]);
if(vis[lxt[i]]&&pd[lxt[i]]&&vis[ver[i]]&&pd[ver[i]]){
printf("%d\n",dis[ver[i]]-dis[lxt[i]]);
}else{
printf("1\n");
}
}
return 0;
}
# 差分约束 # spfa
P1993 小k的农场 题解
P1040 加分二叉树 题解
  • 文章目录
  • 站点概览
qnickx

qnickx

52 日志
5 分类
49 标签
GitHub E-Mail Google
Links
  • 友链页面
  1. 1. 题目链接
  2. 2. 题目描述
  3. 3. 输入格式
  4. 4. 输出格式
  5. 5. 样例输入
  6. 6. 样例输出
  7. 7. 思路
  8. 8. 代码
© 2021 qnickx
由 Hexo 强力驱动 v3.9.0
|
主题 – NexT.Pisces v7.3.0
|
0%