标签:图论-差分约束

题意有 $N$ 个数和 $M_1+M_2$ 种关系。前 $M_1$ 种关系 $(x,y)$ 表示 $S_x+1=S_y$ ,后 $M_2$ 种关系表示 $S_x\le S_y$ 。求最多有多少个数字值。如果无解输出 NIE 。$N\le 600 , M_1+M_2\le 100000$ 。题解不等式关系可以先差分约束建图。边 $(x,y)$ 的权值表示 $S_x-S_y$ 的最大值,对于 $...
题解 图论-最短/最长路 图论-差分约束 图论-Tarjan
省选/NOI-
题意有 $N$ 个重量为 $1,2,3$ 的砝码,以知部分砝码之间的重量关系。给出砝码 $A,B$ ,要求另外选出两个砝码 $C,D$,使得 $A+B > , = , < C+D$ ,求三种情况的方案数。$4\le N\le 50$ 。题解可以先预处理出砝码之间差值的范围。令 $S_i$ 为 $i$ 砝码的重量,用 $mx[i][j]$ 表示 $S_i-S_j$ 的最大值,$mn...
题解 图论-差分约束
省选/NOI-
题意给 $N$ 个人分糖。有 $K$ 个要求,格式为 $(X,A,B)$ ,表示对第 $A$ 个人和第 $B$ 个人有第 $X$ 种限制,用 $S_i$ 表示第 $i$ 个人分得的糖数:$X=1$ , $S_A=S_B$$X=2$ , $S_A<S_B$$X=3$ , $S_A\geq S_B$$X=4$ , $S_A>S_B$$X=5$ , $S_A\le S_B$求最少需要准...
题解 图论-差分约束
提高+/省选-