#P3266. 图上方程组

    ID: 2452 传统题 1000ms 512MiB 尝试: 25 已通过: 10 难度: 6 上传者: 标签>图论线性代数与代数高斯消元数论CF2100数学模运算鸣谢fzszzy制作数据

图上方程组

图上方程组

题目描述

给定一张无向图 G=(V,E)G=(\mathcal V,\mathcal E) 和一个质数 PP。在每条边的两个方向上定义 A(u,v),B(u,v),C(u,v)A(u,v),B(u,v),C(u,v) 三个权值。已知 A,BA,B,求 CC。保证每条边的 BB 均不等于 0 mod P0\bmod P。

每个节点 v∈Vv\in\mathcal V 满足

$$\sum_{q:\,\{v,q\}\in\mathcal E} C(v,q)\equiv0\pmod P .$$

对每条回路 v0,v1,…,vkv_0,v_1,\ldots,v_k,其中 vk=v0v_k=v_0,要求

$$\sum_{i=0}^{k-1} B(v_i,v_{i+1})\,C(v_i,v_{i+1}) \equiv \sum_{i=0}^{k-1}A(v_i,v_{i+1})\pmod P .$$

同一条边的两个方向满足

$$\begin{aligned} A(u,v)&\equiv-A(v,u)\pmod P,\\ B(u,v)&\equiv B(v,u)\pmod P,\\ C(u,v)&\equiv-C(v,u)\pmod P. \end{aligned}$$

输入格式

第一行三个整数 V,E,PV,E,P,表示节点数、边数和模数。节点编号从 11 到 VV。

接下来 EE 行,每行四个整数 x,y,a,bx,y,a,b,表示一条连接 xx 与 yy 的无向边,A(x,y)=aA(x,y)=a,B(x,y)=bB(x,y)=b。反向权值按题目中的关系确定。没有重边或自环。

输出格式

若无解,输出一行 -1。有解时可以输出任意一组解。按输入顺序输出 EE 行,第 ii 行是对应输入方向上的 C(x,y)C(x,y) 在 [0,P−1][0,P-1] 中的代表值。

样例

3 3 7
1 2 15 -6
2 3 22 8
3 1 1 -69
1
1
1

数据规模与约定

V≤100V\le100,E≤2000E\le2000,P≤1018P\le10^{18}。

BZOJ 归档题面