正題

題目鏈接:http://noip.ybtoj.com.cn/contest/105/problem/3

---

題目大意

$n$個點$m$條邊的圖，保證每條邊兩邊的點權和大于等于邊權?，F在要去減去最少/多的點權使得每條邊的邊權等于兩邊的點權。

---

解題思路

對與一個連通塊，顯然確定一個就可以確定別的，但是我們無法枚舉這個。所以我們設第一個為$x$，然后后面的都可以表示成$kx+b$的形式，之后因為每個點的點權有限制，這樣我們就可以確定$x$的范圍。

對與環的情況判斷一下$k_{1}x+b_1=k_{2}x+b_2$的方程解的情況即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define ll long long using namespace std; const ll N=5e5+10; struct node{ll to,next,w; }a[N*12]; ll n,m,p[N],k[N],b[N],sumk,sumb; ll l,r,maxs,mins,tot,ls[N]; bool v[N],vis[N]; ll read() {ll x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } ll check(ll K,ll B,ll x){if((K-k[x])==0){if(b[x]-B)return 0;return 1;}if((b[x]-B)%(K-k[x])!=0)return 0;ll w=(b[x]-B)/(K-k[x]);if(l>w||w>r)return 0;l=w;r=w;return 1; } bool dfs(ll x){v[x]=1;sumk+=k[x];sumb+=b[x];if(k[x]==1){l=max(l,-b[x]);r=min(r,p[x]-b[x]);if(l>r)return 0;}else{l=max(l,b[x]-p[x]);r=min(r,b[x]);if(l>r)return 0;}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(v[y]){if(!check(-k[x],a[i].w-b[x],y))return 0;}else{k[y]=-k[x];b[y]=a[i].w-b[x];if(!dfs(y))return 0;}}return 1; } int main() { // freopen("diamond.in","r",stdin); // freopen("diamond.out","w",stdout);n=read();m=read();ll sum=0;for(ll i=1;i<=n;i++)sum+=(p[i]=read());for(ll i=1;i<=m;i++){ll x=read(),y=read(),w=read();addl(x,y,w);addl(y,x,w);}for(ll i=1;i<=n;i++){if(v[i])continue;l=sumk=sumb=0;r=p[i];k[i]=1; if(!dfs(i))return printf("NIE\n")&0;else{if(sumk<0)maxs+=l*sumk+sumb,mins+=r*sumk+sumb;else maxs+=r*sumk+sumb,mins+=l*sumk+sumb;}}printf("%lld %lld\n",sum-maxs,sum-mins); }

總結

以上是生活随笔為你收集整理的YbtOJ#20073-[NOIP2020模拟赛B组Day6]钻石守卫【构造】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。