M_sea

CF241E Flights
CodeforcesLuogu分析首先找到所有在 $1\to n$ 路径上的边,那么其它的边随便是多少都可以。你甚...
扫描右侧二维码阅读全文
13
2019/07

CF241E Flights

Codeforces

Luogu

分析

首先找到所有在 $1\to n$ 路径上的边,那么其它的边随便是多少都可以。你甚至可以 rand 一个边权

设 $dis_i$ 表示 $1$ 到 $i$ 的最短路长度,那么对于一条边 $(u,v)$ 有 $1\leq dis_v-dis_u\leq 2$ 。直接差分约束连边判断即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
 
const int N=1000+10,M=5000+10;
 
int n,m,a[M],b[M];
 
struct edge { int v,w,nxt; } e[M<<1];
int head[N];
 
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
 
vector<int> E[N];
 
int vis[N],in[N];
inline int dfs(int u) {
    if (vis[u]) return in[u];
    vis[u]=1;
    if (u==n) return in[u]=1;
    for (re int v:E[u])
        if (dfs(v)) in[u]=1;
    return in[u];
}
 
int dis[N],inq[N],cnt[N];
inline int spfa() {
    queue<int> Q; memset(dis,0x3f,sizeof(dis));
    Q.push(1); dis[1]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w,cnt[v]=cnt[u]+1;
                if (cnt[v]>n) return 1;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return 0;
}
 
int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        a[i]=read(),b[i]=read();
        E[a[i]].push_back(b[i]);
    }
    dfs(1);
    for (re int u=1;u<=n;++u) {
        if (!in[u]) continue;
        for (re int v:E[u]) {
            if (!in[v]) continue;
            addEdge(u,v,2),addEdge(v,u,-1);
        }
    }
    if (spfa()) { puts("No"); return 0; }
    puts("Yes");
    for (re int i=1;i<=m;++i) {
        if (!in[a[i]]||!in[b[i]]) puts("1");
        else printf("%d\n",dis[b[i]]-dis[a[i]]);
    }
    return 0;
}
最后修改:2019 年 07 月 13 日 11 : 22 AM

发表评论