Solution [POI2012]BEZ-Minimalist Security
题目大意：给定一张无向图。保证初始边权 (leq) 两端点点权之和。将每个点的点权减小，代价为前后的点权差的绝对值，修改后要求所有边权等于两端点点权之和，且修改后点权非负。求最大与最小代价。
bfs、人类智慧
分析：
首先限制条件可以转化，如果有边 ((i,j,d))，两点点权为 (v[i],v[j])，设 (i,j) 两点的代价为(X_i,X_j)
有(X_i+X_j=v[i]+v[j]-d quad X_iin [0,v[i]],X_jin [0,v[j]])
充分发挥人类智慧，由于不同连通块之间是互不影响的，我们分开计算
对于一个连通块，我们将任意一点的代价设为 (x)，我们一遍 (bfs) 就可以将每个点的代价用 (x) 表示出来
这个过程中有一些特殊情况，如果遇到了已经 (bfs) 过的点，我们直接联立解方程，判断有解、无解或者无数解
(1.)有解，直接解出(x)，如果连通块内的解互不冲突，逐一带入验证
(2.)无解，原问题也一定无解
(3.)无数解，这个比较麻烦，我们(bfs)结束之后如果仍可以有无数解，我们对每个点的代价解不等式求交集，就可以求出(x)的取值范围。随后取端点值代入，求出最大最小值
（我也不知道为啥写了这么长而且丑陋）
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100,maxm = 6e6 + 100,inf = 0x7fffffff;
namespace FastIO{
typedef int type;
const int bufsize = 65536;
char buf[bufsize],*s,*t;
inline char gc(){
if(s == t)s = buf,t = buf + fread(buf,sizeof(char),bufsize,stdin);
return *(s++);
}
inline type read(){
type ret = 0;char c = gc();
while(c < '0' || c > '9')c = gc();
while(c >= '0' && c <= '9'){
ret = ret * 10 + c - '0';
c = gc();
}
return ret;
}
}
using FastIO::read;
struct seg{ll l,r;};
struct mpair{ll fir,sec;};
inline seg merge(seg a,seg b){
return seg{max(a.l,b.l),min(a.r,b.r)};
}
struct poly{
ll a,b;
inline seg solve(int x)const{
if(a > 0)return seg{-b / a,(x - b) / a};
if(a < 0)return seg{(x - b) / a,-b / a};
}
inline ll calc(ll x)const{
return a * x + b;
}
inline poly operator - (const poly &rhs)const{
return poly{a - rhs.a,b - rhs.b};
}
inline poly operator + (const poly &rhs)const{
return poly{a + rhs.a,b + rhs.b};
}
}p[maxn];
inline int solve(poly a,poly b){//-inf:nosol inf:multisol
if(a.a == b.a){
if(b.b == a.b)return inf;
else return -inf;
}
if((b.b - a.b) % (a.a - b.a))return -inf;
return (b.b - a.b) / (a.a - b.a);
}
int vis[maxn],n,m,val[maxn];
ll ans1,ans2;
struct edge{int u,v,d;}edges[maxm];
int head[maxn],nxt[maxm],tot;
inline void addedge(int u,int v,int d){
edges[++tot] = edge{u,v,d};
nxt[tot] = head[u];
head[u] = tot;
}
vector<int> vec;
inline int bfs(int s){
int res = inf;
p[s] = poly{1,0};
queue<int> q;
q.push(s);
vec.clear();
vec.push_back(s);vis[s] = 1;
while(!q.empty()){
int u = q.front();q.pop();
for(int i = head[u];i;i = nxt[i]){
const edge &e = edges[i];
if(!vis[e.v]){
p[e.v] = poly{0,e.d} - p[u];
q.push(e.v);
vis[e.v] = 1;
vec.push_back(e.v);
}else{
int tmp = solve(poly{0,e.d} - p[u],p[e.v]);
if(tmp != inf){
if(res != inf && res != tmp)return -inf;
res = tmp;
}
}
}
}
return res;
}
inline mpair solve(int org){
if(org != inf){
for(int x : vec)
if(p[x].calc(org) < 0 || p[x].calc(org) > val[x])return mpair{-inf,-inf};
ll res = 0;
for(int x : vec)res += p[x].calc(org);
return mpair{res,res};
}
seg res = seg{-inf,inf};
for(int x : vec)res = merge(res,p[x].solve(val[x]));
if(res.l > res.r)return mpair{-inf,-inf};
poly now = poly{0,0};
for(int x : vec)now = now + p[x];
return mpair{min(now.calc(res.l),now.calc(res.r)),max(now.calc(res.l),now.calc(res.r))};
}
int main(){
n = read(),m = read();
for(int i = 1;i <= n;i++)val[i] = read();
for(int u,v,d,i = 1;i <= m;i++){
u = read(),v = read(),d = read();
addedge(u,v,val[u] + val[v] - d);
addedge(v,u,val[u] + val[v] - d);
}
for(int i = 1;i <= n;i++)
if(!vis[i]){
int res = bfs(i);
if(res == -inf)return puts("NIE"),0;
else{
mpair tmp = solve(res);
if(tmp.fir == -inf)return puts("NIE"),0;
ans1 += tmp.fir;
ans2 += tmp.sec;
}
}
printf("%lld %lld
",ans1,ans2);
return 0;
}