CF1450E

差分约束板子。

因为相邻差绝对值为 $1$ ，所以有奇环一定无解。

$a_i+1=a_j$ 很好处理，关键在于 $|a_i-a_j|=1$ 。

对于 $|a_i-a_j|=1$ ，拆成两个条件： $a_i \leq a_j+1$和$a_i \geq a_j-1$ 。

枚举起点，特判有连边的点的最短路相等即可。

为什么呢？因为 $d_i=d_j$ 意味着起点到 $i$ 与 $j$ 距离相等， $i$ ，起点， $j$ 形成长度为偶数的路径，又因为 $i$ ， $j$ 有边，所以存在奇环。

这题评2700原因应该是外国人不知道差分约束。

代码：

#include
#include
#include
using namespace std;

int n,m,g[200][200];
int a[2000],b[2000],c;

int main(void)
{
    memset(g,0x3f,sizeof(g));
    scanf("%d%d",&n,&m);
    for(int i=0;i){
        scanf("%d%d%d",&a[i],&b[i],&c);
        g[a[i]-1][b[i]-1]=1;
        if(c==1) g[b[i]-1][a[i]-1]=-1;
        else g[b[i]-1][a[i]-1]=1;
    }
    for(int i=0;i)
        g[i][i]=0;
    for(int i=0;i)
        for(int j=0;j)
            for(int k=0;k)
                g[j][k]=min(g[j][k],g[j][i]+g[i][k]);
    int pos=-1,ans=-1;
    for(int i=0;i){
        if(g[i][i]<0){
            printf("NO\n");
            return 0;
        }
        int mx=-n,mn=n;
        for(int j=0;j){
            mx=max(mx,g[i][j]);
            mn=min(mn,g[i][j]);
        }
        for(int j=0;j)
            if(g[i][a[j]-1]==g[i][b[j]-1])
                mx=-n;
        if(ansmn){
            ans=mx-mn; pos=i;
        }
    }
    if(ans==-1) printf("NO\n");
    else{
        printf("YES\n%d\n",ans);
        for(int i=0;i)
            printf("%d%c",g[pos][i]+n,i==n-1?'\n':' ');
    }
    return 0;
}
/*
*/