学步园

给出一个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。

Sample Input 1
3 2
5 10 5
1 2 5
2 3 3

 

Sample Input 2
3 3
1 1 1
1 2 1
1 3 1
3 2 1

Sample Output 1
12 15

Sample Output 2
NIE

看题解有说道用【裸的】并查集，下了两份代码，思路貌似一样，都没看懂

Code1:4032ms

#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define LL long long
struct edge{
	int d,s,w;
}e[1<<23];
queue <int> q;
int lst[524288],gs,n,m;
LL ami=0,ama=0;
int x,y,w;
int p[524288];
LL a[524288];
LL b[524288];
int v[524288];
void no_sol(){
	printf("NIE\n");
	exit(0);
}
void insert(int x,int y,int w){
	e[++gs].d=y;
	e[gs].s=lst[x];
	e[gs].w=w;
	lst[x]=gs;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",p+i);
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d",&x,&y,&w);
		insert(x,y,p[x]+p[y]-w);
		insert(y,x,p[x]+p[y]-w);
	}
	for (int i=1;i<=n;i++)
		if (!v[i]) {
			v[i]=true;
			LL mi=0,ma=p[i];
			a[i]=1;
			b[i]=0;
			LL sa=1,sb=0;
			while (!q.empty()) q.pop();
			q.push(i);
			while (!q.empty()) {
				int now=q.front();
				q.pop();
				for (int j=lst[now];j>0;j=e[j].s)
					if (!v[e[j].d]) {
						v[e[j].d]=true;
						a[e[j].d]=-a[now];
						b[e[j].d]=(LL)e[j].w-b[now];
						sa+=(LL)a[e[j].d];
						sb+=(LL)b[e[j].d];
						if (a[e[j].d]==1) {
							mi=max(mi,-b[e[j].d]);
							ma=min(ma,p[e[j].d]-b[e[j].d]);
						}
						else {
							ma=min(ma,b[e[j].d]);
							mi=max(mi,b[e[j].d]-p[e[j].d]);
						}
						q.push(e[j].d);
					}
					else {
						if (a[now]!=a[e[j].d]) {
							if (b[now]+b[e[j].d]!=e[j].w) no_sol();
						}
						else {
							if ((e[j].w-b[now]-b[e[j].d])%2!=0) no_sol();
							mi=max(mi,(e[j].w-b[now]-b[e[j].d])/(2*a[now]));
							ma=min(ma,(e[j].w-b[now]-b[e[j].d])/(2*a[now]));
						}
					}
				if (mi>ma) no_sol();
			}
			LL v1=(LL)mi*sa+sb,v2=(LL)ma*sa+sb;
			ami+=min(v1,v2);
			ama+=max(v1,v2);
		}
	printf("%lld %lld\n",ami,ama);
	return 0;
}

Code2:4343ms

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct node {
	int data, weight;
	node *next;
} *ge[500000];
pair<long long, long long> val[500000];
int queue[500000], w[500000];
bool v[500000];
void insertEdge(int a, int b, int w) {
	static node buf[6000000];
	static int top = 0;
	node *p = &buf[top ++];
	p->data = b;
	p->weight = w;
	p->next = ge[a];
	ge[a] = p;
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i ++) {
		ge[i] = 0;
		scanf("%d", &w[i]);
	}
	for (int i = 0; i < m; i ++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a --;
		b --;
		insertEdge(a, b, w[a] + w[b] - c);
		insertEdge(b, a, w[a] + w[b] - c);
	}	
	long long ans1 = 0, ans2 = 0;
	memset(v, false, sizeof(v));
	for (int i = 0; i < n; i ++)
		if (! v[i]) {
			v[i] = true;
			queue[0] = i;
			val[i] = make_pair(1LL, 0LL);
			int tot = 1;
			long long L = 0, R = w[i];
			pair<long long, long long> sum = make_pair(1LL, 0LL);
			for (int head = 0, tail = 1; head < tail; head ++) {
				int now = queue[head];
				for (node *p = ge[now]; p; p = p->next)
					if (! v[p->data]) {
						v[p->data] = true;
						queue[tail ++] = p->data;
						val[p->data] = make_pair(-val[now].first, p->weight - val[now].second);
						if (val[p->data].first == 0 && (0 > val[p->data].second || val[p->data].second > w[p->data])) {
							printf("NIE\n");
							return 0;
						}
						if (val[p->data].first > 0) {
							L = max(L, (-val[p->data].second - 1) / val[p->data].first + 1);
							R = min(R, (w[p->data] - val[p->data].second) / val[p->data].first);
						}
						if (val[p->data].first < 0) {
							L = max(L, (val[p->data].second - w[p->data] - 1) / (-val[p->data].first) + 1);
							R = min(R, val[p->data].second / (-val[p->data].first));
						}
						if (L > R) {
							printf("NIE\n");
							return 0;
						}
						sum.first += val[p->data].first;
						sum.second += val[p->data].second;
					} else {
						pair<long long, long long> tmp;
						tmp.first = val[now].first + val[p->data].first;
						tmp.second = val[now].second + val[p->data].second;
						if (tmp.first == 0 && tmp.second != p->weight) {
							printf("NIE\n");
							return 0;
						}
						if (tmp.first != 0) {
							if ((p->weight - tmp.second) % tmp.first != 0) {
								printf("NIE\n");
								return 0;
							}
							long long x = (p->weight - tmp.second) / tmp.first;
							L = max(L, x);
							R = min(R, x);
							if (L > R) {
								printf("NIE\n");
								return 0;
							}
						}
					}
			}
			long long t1 = sum.first * L + sum.second;
			long long t2 = sum.first * R + sum.second;
			ans1 += min(t1, t2);
			ans2 += max(t1, t2);
		}	
	printf("%lld %lld\n", ans1, ans2);
}