问题描述
LiLand is a country, consisting of nn cities. The cities are numbered from 1 to nn . The country is well known because it has a very strange transportation system. There are many one-way flights that make it possible to travel between the cities, but the flights are arranged in a way that once you leave a city you will never be able to return to that city again.
Previously each flight took exactly one hour, but recently Lily has become the new manager of transportation system and she wants to change the duration of some flights. Specifically, she wants to change the duration of some flights to exactly 2 hours in such a way that all trips from city 1 to city nn take the same time regardless of their path.
Your task is to help Lily to change the duration of flights.
输入格式
First line of the input contains two integer numbers nn and mm (2<=n<=1000; 1<=m<=5000) specifying the number of cities and the number of flights.
Each of the next mm lines contains two integers a_{i}a**i and b_{i}b**i (1<=a_{i}<b_{i}<=n) specifying a one-directional flight from city a_{i}a**i to city b_{i}b**i . It is guaranteed that there exists a way to travel from city number 1 to city number nn using the given flights. It is guaranteed that there is no sequence of flights that forms a cyclical path and no two flights are between the same pair of cities.
输出格式
If it is impossible for Lily to do her task, print "No" (without quotes) on the only line of the output.
Otherwise print "Yes" (without quotes) on the first line of output, then print an integer ans_{i}ans**i (1<=ans_{i}<=2)(1<=ans**i<=2) to each of the next mm lines being the duration of flights in new transportation system. You should print these numbers in the order that flights are given in the input.
If there are multiple solutions for the input, output any of them.
题意大概
给一张n(n≤1000)个点m(m≤5000)条边的DAG，确定每条边的边wi(wi∈{1,2})，使得所有从1到n的路径拥有相同的长度。
样例输入输出
样例输入1
3 3
1 2
2 3
1 3
样例输出1
Yes
1
1
2
样例输入2
4 4
1 2
2 3
3 4
1 4
样例输出2
No
样例输入3
5 6
1 2
2 3
3 5
1 4
4 5
1 3
样例输出3
Yes
1
1
1
2
1
2
解析
首先注意到的应该是这张图是DAG的特性。可以发现，对于图中的任意一点u，如果u在任意一条1到n的路径上，必须满足从1出发到u的所有路径的长度相同，否则不存在所有1到n的路径长度相同。假设点1到i的距离为(f[i])，那么对与u相连的点v，需要满足(1<=f[v]-f[u]<=2)，转化为差分约束求解。
一个小问题是判断一个点是否在1到n的某一条路径上。可以正着DFS一遍，倒着DFS一遍，如果两次都经过了某一点。说明该点满足上述要求。
代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 1002
#define M 5002
using namespace std;
struct edge{
int u,v;
}e[M];
int head1[N],ver1[M],nxt1[M],l1;
int head2[N],ver2[M],nxt2[M],l2;
int head[N],ver[M*2],nxt[M*2],edge[M*2],l;
int n,m,i,dis[N],cnt[N];
bool vis1[N],vis2[N],vis[N],in[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void insert1(int x,int y)
{
l1++;
ver1[l1]=y;
nxt1[l1]=head1[x];
head1[x]=l1;
}
void insert2(int x,int y)
{
l2++;
ver2[l2]=y;
nxt2[l2]=head2[x];
head2[x]=l2;
}
void insert(int x,int y,int z)
{
l++;
ver[l]=y;
edge[l]=z;
nxt[l]=head[x];
head[x]=l;
}
void dfs1(int x)
{
vis1[x]=1;
for(int i=head1[x];i;i=nxt1[i]){
int y=ver1[i];
if(!vis1[y]) dfs1(y);
}
}
void dfs2(int x)
{
vis2[x]=1;
for(int i=head2[x];i;i=nxt2[i]){
int y=ver2[i];
if(!vis2[y]) dfs2(y);
}
}
bool SPFA()
{
queue<int> q;
memset(dis,-0x3f,sizeof(dis));
q.push(1);
dis[1]=0;in[1]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(dis[y]<dis[x]+edge[i]){
dis[y]=dis[x]+edge[i];
if(!in[y]){
in[y]=1;
cnt[y]++;
q.push(y);
}
if(cnt[y]>n) return 0;
}
}
in[x]=0;
}
return 1;
}
int main()
{
n=read();m=read();
for(i=1;i<=m;i++){
e[i].u=read(),e[i].v=read();
insert1(e[i].u,e[i].v);
insert2(e[i].v,e[i].u);
}
dfs1(1);
dfs2(n);
for(i=1;i<=n;i++) vis[i]=(vis1[i]&vis2[i]);
for(i=1;i<=m;i++){
if(vis[e[i].u]&&vis[e[i].v]){
insert(e[i].u,e[i].v,1);
insert(e[i].v,e[i].u,-2);
}
}
if(!SPFA()){
puts("No");
return 0;
}
puts("Yes");
for(i=1;i<=m;i++){
if(vis[e[i].u]&&vis[e[i].v]) printf("%d
",dis[e[i].v]-dis[e[i].u]);
else puts("1");
}
return 0;
}
总结
还是对差分约束不是很熟悉，导致发现了性质却不知道用差分约束求解。