Codeforces

Luogu

分析

显然构造出来的图满足:对于一条在 $1\to n$ 的某条路径上的边 $(u,v)$,满足 $1\leq dis_v-dis_u\leq 2$。

于是只需要找到所有 $1\to n$ 路径上的边,差分约束建图,然后判负环即可。

最后输出方案时,如果该边在路径上就输出 $dis_v-dis_u$ ,否则随便输出 $1$ 或 $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;

int x[M],y[M];
vector<int> G[N],fG[N];
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;
}

int v1[N],v2[N];
inline void dfs1(int u) { v1[u]=1;
    for (re int v:G[u]) if (!v1[v]) dfs1(v);
}
inline void dfs2(int u) { v2[u]=1;
    for (re int v:fG[u]) if (!v2[v]) dfs2(v);
}

int dis[N],inq[N],cnt[N];
inline int spfa() { memset(dis,0x3f,sizeof(dis));
    queue<int> Q; Q.push(1); dis[1]=0,cnt[1]=1;
    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) { x[i]=read(),y[i]=read();
        G[x[i]].push_back(y[i]),fG[y[i]].push_back(x[i]);
    }
    dfs1(1),dfs2(n);
    for (re int i=1;i<=m;++i) { int u=x[i],v=y[i];
        if (v1[u]&&v2[u]&&v1[v]&&v2[v]) addEdge(u,v,2),addEdge(v,u,-1);
    }
    if (spfa()) puts("No");
    else { puts("Yes");
        for (re int i=1;i<=m;++i) { int u=x[i],v=y[i];
            if (v1[u]&&v2[u]&&v1[v]&&v2[v]) printf("%d\n",dis[v]-dis[u]);
            else puts("1");
        }
    }
    return 0;
}
最后修改:2019 年 10 月 15 日 09 : 50 PM