Rockdu's Blog

【题目描述】

给出一个N个顶点、M条边的无向图，边(u,v)有权值w(u,v)，顶点i也有权值p(i)，

并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。

现在要将顶点i的权值减去z(i)，其中0≤z(i)≤p(i)。

修改后设顶点i的权值p'(i)=p(i)-z(i)，对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。

求sum{z(i)}的最小值和最大值。

【输入】

第一行两个正整数n,m (n≤500,000, m≤3,000,000)。

第二行n个整数，依次表示p(1),p(2),...,p(n) (0≤p(i)≤10^6)。

下面m行，每行三个整数u,v,w (1≤u,v≤n, 0≤w≤10^6)，表示存在一条权值为w的边(u,v)。

【输出】

两个正整数，分别表示sum{z(i)}的最小值和最大值，如果不存在方案就输出NIE。

【输入样例】

For the input data:
3 2
5 10 5
1 2 5
2 3 3
the correct result is:
12 15
whereas for the following input data:
3 3
1 1 1
1 2 1
1 3 1
3 2 1
the correct result is:
NIE

【提示】

很简单的一道题，发现一个点的值定了，那么其它点都确定了。

那么我们把一个点设出来，dfs出一棵树，设根为x。

用树上的边推出所有点关于x的一次函数。

一边dfs点值一边更新x的取值范围

最后再用非树边验证是否满足就可以了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define LL long long
using namespace std;
const int maxn = 3e6 + 5;
struct edge {
	int v, w, next;
} e[maxn << 1];
int head[maxn], cnt, u, v, w;
void adde(const int &u, const int &v, const int &w) {
	e[++cnt] = (edge) {v, w, head[u]};
	head[u] = cnt;
}
int op[maxn], n, m;
LL l, r, x[maxn], c[maxn], ans = 1e18;
LL sumx, sumc, sum, totmx, totmn;
LL k, b;
inline char gc(){
    static char buf[5000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
}
void read(int &x) {
	x = 0; static char c = gc();
	while(!isdigit(c)) c = gc();
	while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}

void ref(LL tl, LL tr) {
	l = max(tl, l), r = min(tr, r);
}

void dfs(int u, int p) {
	sumx += x[u], sumc += c[u], sum += op[u];
	if(x[u] > 0) ref(-c[u], op[u] - c[u]);
	else ref(c[u] - op[u], c[u]);
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		if(x[v]) {
			k = x[u] + x[v], b = e[i].w - c[u] - c[v];
			if(!k) {
				if(b) {
					printf("NIE");
					exit(4);
				}
				continue;
			} 
			if(b % k != 0) {
				printf("NIE");
				exit(3);
			}
			ans = b / k;
			continue;
		}
		x[v] = -x[u];
		c[v] = e[i].w - c[u];
		dfs(v, u);
	}
}

void GetCon(int u) {
	x[u] = 1, sum = sumx = sumc = 0;
	ans = 1e18, l = 0, r = op[u];
	dfs(u, 0);
	if(l > r) {
		printf("NIE");
		exit(4);
	}
	if(ans != 1e18) {
		if(ans < l || ans > r)
			{
				printf("NIE");
				exit(5);
			}
		l = r = ans;
	}
	if(sumx > 0) {
		totmn += sum - (sumx * r + sumc);
		totmx += sum - (sumx * l + sumc);
	} else {
		totmn += sum - (sumx * l + sumc);
		totmx += sum - (sumx * r + sumc);
	}
}

int main() {
	read(n), read(m);
	for(register int i = 1; i <= n; ++i)
		read(op[i]);
	for(register int i = 1; i <= m; ++i) {
		read(u), read(v), read(w);
		adde(u, v, w), adde(v, u, w);
	}
	for(register int i = 1; i <= n; ++i)
		if(!x[i]) GetCon(i);
	printf("%lld %lld", totmn, totmx);
	return 0;
}