[EZOI][1214NOI模拟赛]graph(搜索+数学)

§ 1 题意

给定一个点数为 $n$,边数为 $m$ 的无向图 $G=\lt V,E\gt$。

边 $(i,j)$ 有边权 $w_{i,j}$,点 $i$ 有点权 $p_i$,且对于 $\forall\ (i,j)\in E,\ \ p_i+p_j\geq w_{i,j}$。

现要将顶点 $i$ 的权值减去 $c_i\ (0\leq c_i\leq p_i)$,记修改后点权 $p’_i=p_i-c_i$,对于 $\forall\ (i,j)\in E,\ \ p’_i+p’_j=w_{i,j}$。

求满足条件的 $\sum\limits_{i\in V}c_i$ 的最小值和最大值,如果不存在则输出 ${\rm NIE}$。

保证给出的图中无重边无自环。

$n\leq 500000,\ m\leq 3000000,\ 0\leq p_i\leq 10^6,\ 0\leq w_{i,j}\leq 10^6$。


§ 2 分析

首先令 $w’_{i,j}=p_i+p_j-w_{i,j}$,表示每条边两端点减小的值之和。

考虑一个连通块,若一个点的 $c_i$ 确定,则所有点的 $c_i$ 都能确定。

不妨钦定一个根节点 $s$,令 $c_s=x$,则可 ${\rm bfs}$ 出每个点 $i$ 的 $d_i$ 和 ${\rm sgn}_i\ ({\rm sgn}_i=\pm 1)$ 值使得 $c_i=d_i+{\rm sgn}_i·x$。

若在 ${\rm bfs}$ 过程中若多次访问到同一个点,则需要判断是否矛盾:

  • 设访问边 $(i,j)$ 时两端值均已求出,则有 $c_i=d_i+{\rm sgn}_i·x,\ \ c_j=d_j+{\rm sgn}_j·x,\ \ w’_{i,j}=c_i+c_j$。
    • 若 ${\rm sgn}_i=-{\rm sgn}_j$,则 $w’_{i,j}=d_i+d_j$,若不符合该等式则矛盾,直接输出 ${\rm NIE}$。
    • 若 ${\rm sgn}_i={\rm sgn}_j$,则 $w’_{i,j}=d_i+d_j+2\,{\rm sgn}_i·x$,可以用该方程解出 $x=\frac{w’_{i,j}-d_i-d_j}{2\,{\rm sgn}_i}$,若 $x$ 不为整数或多个类似情况中解出的 $x$ 不同则矛盾,直接输出 ${\rm NIE}$。

对一个连通块 ${\rm bfs}$ 完后,考虑每个点本身的限制:

  • 对于 $\forall\ i\in V,\ \ 0\leq d_i+{\rm sgn}_i·x\leq p_i$,
    • 若 ${\rm sgn}_i = 1$,则化简得 $-d_i\leq x\leq p_i-d_i$。
    • 若 ${\rm sgn}_i = -1$,则化简得 $d_i-p_i\leq x\leq d_i$。

对所有限制取交集得到形如 $\min x\leq x\leq\max x$ 的区间。

若此时 $\min x>\max x$ 则区间为空,输出 ${\rm NIE}$。

若之前有解出过 $x$ 的精确值,则判断 $x$ 是否在区间内,若不在区间内则矛盾,输出 ${\rm NIE}$。

最后答案为 $\sum\limits_{i\in V}c_i=\sum\limits_{i\in V}d_i+x\sum\limits_{i\in V}{\rm sgn}_i$,是一个常数或一次函数,易于统计最大值和最小值。

总时间复杂度为 $O(n+m)$。


注意 && 是短路运算符,原来第 $42\sim44$ 行写了

1
2
3
if(x & 1) koware();
if(~defx && (x >>= 1) != defx) koware();
defx = x;

结果 ${\rm WA}$ 成 $65$ 分 $(っ °Д °;)っ$,改成如下就 ${\rm AC}$ 了

1
2
3
if(x & 1) koware(); else x >>= 1;
if(~defx && x != defx) koware();
defx = x;


§ 3 代码

注:c[i] 表示本文中的 ${\rm sgn}_i$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXV = 500005, MAXE = 6000005;

inline void getint(int &num){
register int ch, neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}

template <typename T> inline void checkmax(T &a, const T &b) {if(a < b) a = b;}
template <typename T> inline void checkmin(T &a, const T &b) {if(b < a) a = b;}

int n, m, p[MAXV], q[MAXV], c[MAXV];
ll d[MAXV], minans, maxans; bool vis[MAXV];
struct Edge {int np, val; Edge *nxt;} E[MAXE], *V[MAXV];

inline void addedge(const int &u, const int &v, const int &w){
static int tope = 0;
E[++tope].np = v, E[tope].val = w, E[tope].nxt = V[u], V[u] = E + tope;
}

inline void koware() {puts("NIE"), exit(0);}

inline void bfs(const int &s){
register int l = 0, r = 1, defx = -1; q[0] = s, c[s] = 1;
while(l < r){
const int &u = q[l++]; vis[u] = 1;
for(register Edge *ne = V[u]; ne; ne = ne->nxt){
if(!c[ne->np]) c[ne->np] = -c[u], d[ne->np] = ne->val - d[u], q[r++] = ne->np;
else if(!vis[ne->np]){
if(c[u] == c[ne->np]){
register ll x = (ne->val - d[u] - d[ne->np]) * c[u];
if(x & 1) koware(); else x >>= 1;
if(~defx && x != defx) koware();
defx = x;
}
else if(d[u] + d[ne->np] != ne->val) koware();
}
}
}
register ll minx = 0, maxx = p[s], sumc = 1, sumd = 0;
for(register int i = 1; i < r; i++){
const int &u = q[i];
if(c[u] == 1) checkmax(minx, -d[u]), checkmin(maxx, p[u] - d[u]);
else checkmax(minx, d[u] - p[u]), checkmin(maxx, d[u]);
sumc += c[u], sumd += d[u];
}
if(minx > maxx) koware();
if(~defx){
if(defx < minx || defx > maxx) koware();
minans += sumc * defx + sumd, maxans += sumc * defx + sumd;
}
else{
if(sumc >= 0) minans += sumc * minx + sumd, maxans += sumc * maxx + sumd;
else minans += sumc * maxx + sumd, maxans += sumc * minx + sumd;
}
}

int main(){
getint(n), getint(m);
for(register int i = 1; i <= n; i++) getint(p[i]);
for(register int i = 1; i <= m; i++){
int u, v, w; getint(u), getint(v), getint(w);
addedge(u, v, p[u] + p[v] - w), addedge(v, u, p[u] + p[v] - w);
}
for(register int i = 1; i <= n; i++) if(!vis[i]) bfs(i);
return printf("%lld %lld\n", minans, maxans), 0;
}