题解：CF1450E Capitalism

ningago · 2024-04-09 15:52:54 · 题解

不需要使用定理或结论的无脑做法。

显然如果图不是二分图则一定无解。

题目中的 |a_u-a_v|=1 中会出现 a_u=a_v 的情况，不好处理（实际上根据定理并不会出现）。

而此时可以利用二分图的性质，假设 a_u 是偶数点，那么令 a_u=2b_u,a_v=2b_v+1，即可将 |a_u-a_v|\leq 1 转化为 b_v\leq b_u\leq b_v+1，这样差值内的整数就只有 0/1 了。

对特殊边也做相似的转化。由于需要让极差尽可能的大，而差分约束就是在满足最短路的约束下，尽可能让 dis 大。所以枚举一个零势点，跑差分约束即可。

复杂度 O(n^3)。

#define N 2010
int n, m;
int col[N];
int h[N], e[N << 1], ne[N << 1], idx = -1;
void add_edge(int x, int y) { ne[++idx] = h[x], h[x] = idx, e[idx] = y; }
void add(int x, int y) { add_edge(x, y), add_edge(y, x); }
int x_[N], y_[N], z_[N];

void paint(int k, int c)
{
    col[k] = c;
    for(int i = h[k]; ~i; i = ne[i])
    {
        int nx = e[i];
        if(!~col[nx]) paint(nx, col[k] ^ 1);
        else if(col[nx] == col[k]) { printf("NO\n"); exit(0); }
    }
}
int dis[N][N];

void solve()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(h, idx = -1, sizeof(h));
    n = read(), m = read();
    for(int i = 1; i <= m; i++) x_[i] = read(), y_[i] = read(), z_[i] = read(), add(x_[i], y_[i]);
    for(int i = 1; i <= n; i++) col[i] = -1, dis[i][i] = 0;
    paint(1, 0);
    for(int i = 1; i <= m; i++)
    {
        int x = x_[i], y = y_[i], z = z_[i];
        if(col[x] > col[y]) z = -z, x ^= y ^= x ^= y;
        if(z > 0) { ckmin(dis[x][y], 0);  ckmin(dis[y][x], 0); }
        if(z < 0) { ckmin(dis[x][y], -1); ckmin(dis[y][x], 1); }
        if(!z)    { ckmin(dis[x][y], 0);  ckmin(dis[y][x], 1); }
    }
    for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
        ckmin(dis[i][j], dis[i][k] + dis[k][j]);
    for(int i = 1; i <= n; i++) if(dis[i][i] < 0) { printf("NO\n"); return; }
    int mxdt = -1;
static int ans[N], b[N];
    for(int S = 1; S <= n; S++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(!col[i]) b[i] = dis[S][i] * 2;
            else b[i] = dis[S][i] * 2 + 1;
        }
        int mx = *std::max_element(b + 1, b + 1 + n);
        int mn = *std::min_element(b + 1, b + 1 + n);
        if(mx - mn > mxdt)
        {
            mxdt = mx - mn;
            for(int i = 1; i <= n; i++) ans[i] = b[i] - mn;
        }
    }
    printf("YES\n");
    print(mxdt, '\n');
    for(int i = 1; i <= n; i++) print(ans[i], ' ');
    putc('\n');
}