P5590&&CF241E 赛车游戏 题解

发表于 分类于 ， 阅读次数：

题目链接

传送门

题目描述

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;
}
0%