【BZOJ1202】【HNOI2005】狡猾的商人

时间:2024-03-25 22:37:20

查分约束好,好写好调好AC!

原题:

刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了n个月以来的收入情况,其中第i 个月的收入额为Ai(i=1,2,3...n-1,n), 。当 Ai大于0时表示这个月盈利Ai 元,当 Ai小于0时表示这个月亏损Ai 元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。 刁姹的任务是秘密进行的,为了调查商人的账本,她只好跑到商人那里打工。她趁商人不在时去偷看账本,可是她无法将账本偷出来,每次偷看账本时她都只能看某段时间内账本上记录的收入情况,并且她只能记住这段时间内的总收入。 现在,刁姹总共偷看了m次账本,当然也就记住了m段时间内的总收入,你的任务是根据记住的这些信息来判断账本是不是假的。

n < 100,m < 1000

这题可以查分约束也可以用并查集,不过并查集的做法比较神奇,我暂时还不能理解,所以用差分约束水

a到b的收益为w,另sa等于从开始到a的收益,那么sb-s(a-1)=w

因为这本质是一个前缀和,所以要-1

差分约束搞即可

代码:

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct ddd{int nxt,y,v;}e[]; int lk[],ltp=;
inline void ist(int x,int y,int z){e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z;}
int n,m;
int dstc[],cnt[];
int q[],tp=,hd=,tl=; bool vstd[];
bool spfa(){
hd=,tl=;
for(int i=;i<=n;++i) q[++hd]=i,vstd[i]=true,cnt[i]=,dstc[i]=;
while(tl!=hd){
tl=(tl==tp ? : tl+);
for(int i=lk[q[tl]];i;i=e[i].nxt)if(dstc[q[tl]]+e[i].v>dstc[e[i].y]){
dstc[e[i].y]=dstc[q[tl]]+e[i].v;
if(++cnt[e[i].y]==n) return false;
if(!vstd[e[i].y]) q[hd=(hd==tp ? : hd+)]=e[i].y,vstd[e[i].y]=true;
}
vstd[q[tl]]=false;
}
return true;
}
void clr(){ memset(lk,,sizeof(lk)),ltp=;}
int main(){//freopen("ddd.in","r",stdin);
int T; cin>>T; while(T--){ clr();
n=rd(),m=rd();
int l,r,v;
while(m--){
l=rd(),r=rd(),v=rd();
ist(l-,r,v),ist(r,l-,-v);
}
if(spfa()) printf("true\n");
else printf("false\n");
}
return ;
}