bzoj1202[HNOI2005]狡猾的商人

題意：

賬本上記錄了n個月以來的收入情況，其中第i 個月的收入額為Ai 。所謂一段時間內(nèi)的總收入，就是這段時間內(nèi)每個月的收入額的總和。給出m段時間內(nèi)的總收入，判斷賬本是否合法。

題解：

太神了，并查集還能這么用。每月作為一個節(jié)點，同時保存父節(jié)點表示的月份到該月份的盈利是多少，每次讀入一個區(qū)間，如果左右端點在同一個集合內(nèi)，就直接比較兩個節(jié)點的權(quán)值差（因為路徑壓縮時已經(jīng)使它們的父節(jié)點相同），注意路徑壓縮時要先遞歸再維護權(quán)值。如果左右端點在不同集合，則合并，設(shè)所在子樹被合并的那個端點為a2，另一個為a1，a2的根節(jié)點為a5，給出的信息為a3，則a5的權(quán)值變?yōu)閣[a5]=w[a1]-w[a2]+a3。因為：設(shè)a1根節(jié)點為a4，s[i]表示i的前綴和，則w[a1]=s[a1]-s[a4] w[a2]=s[a2]-s[a5] a3=s[a2]-s[a1] 顯然s[a5]-s[a4]=w[a1]-w[a2]+a3=w[a5]。

代碼：

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 using namespace std; 6 7 int fa[1000],w[1000]; 8 int find(int x){if(x==fa[x])return x;else{int y=find(fa[x]); w[x]+=w[fa[x]]; return fa[x]=y;};} 9 int main(){ 10 int t,n,m; scanf("%d",&t); 11 while(t--){ 12 scanf("%d%d",&n,&m); inc(i,0,n)fa[i]=i,w[i]=0; bool f=0; 13 inc(i,1,m){ 14 int a1,a2,a3; scanf("%d%d%d",&a1,&a2,&a3); a1--; 15 int a4=find(a1),a5=find(a2); 16 if(a4==a5&&a3!=w[a2]-w[a1]){printf("false\n");f=1;break;} 17 if(a4!=a5)w[a5]=w[a1]-w[a2]+a3,fa[a5]=a4; 18 } 19 if(!f)printf("true\n"); 20 } 21 }

?

20160401

轉(zhuǎn)載于:https://www.cnblogs.com/YuanZiming/p/5693050.html

總結(jié)

以上是生活随笔為你收集整理的bzoj1202[HNOI2005]狡猾的商人的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。