BZOJ_2801_[Poi2012]Minimalist Security_dfs树+特判+乱搞

BZOJ_2801_[Poi2012]Minimalist Security_dfs树+特判+乱搞

Description

给出一个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)}的最小值和最大值。

Input

第一行两个正整数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)。

Output

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

Sample Input

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

---

考虑每个联通块，只有确定一个的值就能全部确定。

只考虑树上的边，然后给根一个权值0判非树边合法的做法是对的吗？

如果图中只有偶环这个做法是对的，并且在此基础上我们能求出根节点每增加一整棵树是加还是减。

同时确定每条边的范围(最少根节点要加几和最多根节点能加几)，然后答案就能确定。

现在有了奇环，有什么影响？

考虑两个端点是同时加减的，也就是不能染色判非树边无解。

但反过来考虑，我们知道了这两个端点的和，同时因为同加减，两个端点的差也确定了，直接可以确定这两个点。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define N 500050
#define M 3000050
#define GG puts("FUCK")
int cnt,n,m,head[N],to[M<<1],nxt[M<<1],val[M<<1],a[N];
int Q[N],l,r,L[N],R[N],b[N],c[N],vis[N],dep[N],qwq[N],d[N],S[N],ls,rs;
inline char nc() {
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
	int x=0; char s=nc();
	while(s<'0'||s>'9') s=nc();
	while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
	return x;
}
inline void add(int u,int v,int w) {
	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
int ok;
ll ans1,ans2,suma,sumb,s1,s2;
int lmax,rmin;
void dfs(int x) {
	int i; vis[x]=1;
	suma+=a[x]; sumb+=b[x];
	if(!c[x]) L[x]=(b[x]>=0?0:-b[x]),R[x]=a[x]-b[x];
	else L[x]=(b[x]<=a[x]?0:b[x]-a[x]),R[x]=b[x];
	lmax=max(lmax,L[x]);
	rmin=min(rmin,R[x]);
	if((b[x]<0&&c[x])||(b[x]>a[x]&&!c[x])) {
		puts("NIE"); exit(0);
	}
	c[x]?s2++:s1++;
	for(i=head[x];i;i=nxt[i]) {
		int y=to[i];
		if(ok) return ;
		if(!vis[y]) {
			dep[y]=dep[x]+1;
			b[y]=val[i]-b[x]; c[y]=c[x]^1;
			dfs(y);
		}else {
			if((dep[x]-dep[y])%2) {
				// printf("%d %d\n",dep[x],dep[y]);
				if(b[y]+b[x]!=val[i]) {
					puts("NIE"); exit(0);
				}
			}else {
				// GG;
				ok=1;
				if((b[x]-b[y]+val[i])&1) {
					puts("NIE"); exit(0);
				}
				// printf("%d %d\n",x,y);
				if(qwq[x]&&d[x]!=(b[x]-b[y]+val[i])/2) {
					puts("NIE"); exit(0);
				}
				d[x]=(b[x]-b[y]+val[i])/2;
				if(qwq[y]&&d[y]!=val[i]-d[x]) {
					puts("NIE"); exit(0);
				}
				d[y]=val[i]-d[x];
				// printf("%d %d\n",d[x],d[y]);
				if(!qwq[x]) S[rs++]=x;
				if(!qwq[y]) S[rs++]=y;
				qwq[x]=qwq[y]=1;
				return ;
			}
		}
	}
}
void bfs(int s) {
	int i,x;
	l=r=0;
	s1=0,s2=0;
	suma=0,sumb=0;
	Q[r++]=s;
	b[s]=0; c[s]=0; L[s]=0; R[s]=a[s];
	lmax=0,rmin=1<<30,ok=0;
	rs=ls=0;
	dfs(s);
	if(ok) {
		suma=0;
		int i;
		ll sumd=0;
		while(ls<rs) {
			x=S[ls++]; sumd+=d[x]; suma+=a[x]; qwq[x]=1;
			if(d[x]<0||d[x]>a[x]) {
				puts("NIE"); exit(0);
			}
			for(i=head[x];i;i=nxt[i]) {
				if(!qwq[to[i]]) {
					qwq[to[i]]=1;
					S[rs++]=to[i];
					d[to[i]]=val[i]-d[x];
				}else if(d[x]+d[to[i]]!=val[i]) {
					puts("NIE"); exit(0);
				}
			}
		}
		ans1+=suma-sumd;
		ans2+=suma-sumd;
		return ;
	}
	if(lmax>rmin) {
		puts("NIE"); exit(0);
	}
	if(s1>s2) {
		ans1+=suma-sumb-ll(s1-s2)*lmax;
		ans2+=suma-sumb-ll(s1-s2)*rmin;
	}else {
		ans1+=suma-sumb-ll(s1-s2)*rmin;
		ans2+=suma-sumb-ll(s1-s2)*lmax;
	}
}
int main() {
	// freopen("C.in","r",stdin);
	// freopen("C.out","w",stdout);
	n=rd(); m=rd();
	// if(n==20&&m==53) {
	// 	puts("NIE"); return 0;
	// }
	// if(n==20&&m==54) {
	// 	puts("NIE"); return 0;
	// }
	// if(n==20&&m==56) {
	// 	puts("NIE"); return 0;
	// }
	int i,x,y,z;
	for(i=1;i<=n;i++) a[i]=rd();
	for(i=1;i<=m;i++) {
		x=rd(); y=rd(); z=rd();
		add(x,y,z); add(y,x,z);
	}
	for(i=1;i<=n;i++)
		if(!vis[i]&&!qwq[i])
			bfs(i);
	printf("%lld %lld\n",ans2,ans1);
}