正題

---

題目大意

$n$個點$n$條邊的圖，每條邊的邊權為兩個連接節點的權值和，給出所有邊權，求每個節點權值（保證唯一的環為奇環）

---

解題思路

首先并查集找到環上相鄰的兩個點，然后可以發現這兩個點之間有兩個關系（也就是兩條路徑）可以求出其中一個點的權值，然后推出其他點的權值即可

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; struct node{ll to,next,w; }a[N*2]; ll n,fa[N],w[N],ls[N],tot,p1,p2,val; ll find(ll x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void dfs(ll x,ll fa,ll dis){if(x==p2){w[p1]=(val-dis)/2;return;}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x,a[i].w-dis);} } void solve(ll x,ll fa){for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;w[y]=a[i].w-w[x];solve(y,x);} } int main() { int size = 256 << 20; //250M char*p=(char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p) );scanf("%lld",&n);for(ll i=1;i<=n;i++)fa[i]=i;for(ll i=1;i<=n;i++){ll x,y,Fa,Fb,w;scanf("%lld%lld%lld",&x,&y,&w);Fa=find(x);Fb=find(y);if(Fa<Fb)swap(Fa,Fb);if(Fa==Fb)p1=x,p2=y,val=w;else addl(x,y,w),addl(y,x,w),fa[Fa]=Fb;}dfs(p1,0,0);solve(p1,0);for(ll i=1;i<=n;i++)printf("%lld\n",w[i]); }

總結

以上是生活随笔為你收集整理的nssl1487-图的全部內容，希望文章能夠幫你解決所遇到的問題。

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