33OJ
登录 注册

#P17588. UTVPI

    ID: 20292 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>Special Judge最短路2-SAT强连通分量差分约束

UTVPI

题目描述

有 nn 个未知数 x1,x2,…,xnx_1,x_2,\dots,x_n,和 mm 个限制 aixdi+bixei≤cia_ix_{d_i}+b_ix_{e_i}\le c_i,其中 ai,bi∈{1,−1}a_i,b_i\in\{1,-1\}。

判断是否存在一组整数解,如果存在,需要给出任意一组在 int 范围内的解。

输入格式

第一行,输入两个整数 n,mn,m。

接下来 mm 行,每行输入五个整数 ai,bi,ci,di,eia_i,b_i,c_i,d_i,e_i 表示一个限制。

输出格式

一行,nn 个数,表示 x1,x2⋯xnx_1 , x_2 \cdots x_n 的一组可行整数解,如果有多组解,请输出任意一组,无解请输出 No。

2 4
1 1 3 1 2
1 -1 1 1 2
-1 1 1 1 2
-1 -1 0 1 2
1 1
2 4
1 -1 0 1 2
-1 1 0 1 2
1 1 1 1 2
-1 -1 -1 1 2
No

提示

1≤n,m≤5×1031\le n,m\le 5\times 10^3,1≤di,ei≤n1\le d_i,e_i\le n,ai,bi∈{1,−1}a_i,b_i\in\{1,-1\},−105≤ci≤105-10^5\le c_i\le 10^5。不保证 di≠eid_i\neq e_i。