狡猾的商人 [HNOI2005] [一题双解]

Description

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

Input

第一行为一个正整数w，其中w < 100，表示有w组数据，即w个账本，需要你判断。每组数据的第一行为两个正整数n和m，其中n < 100，m < 1000，分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。接下来的m行表示刁姹偷看m次账本后记住的m条信息，每条信息占一行，有三个整数s，t和v，表示从第s个月到第t个月（包含第t个月）的总收入为v，这里假设s总是小于等于t。

Output

包含w行,每行是true或false,其中第i行为true当且仅当第i组数据，即第i个账本不是假的；第i行为false当且仅当第i组数据，即第i个账本是假的。

Sample Input

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

Sample Output

true
false

Solution

思路一：带权并查集

给出[l,r]的区间和，相当于s[r]-s[l]

一旦已经知道了 s[a]-s[b],s[b]-s[c]，显然再给出一条[a,c]就可以判断"账本的真假"了

将每条这样的信息(l,r,w)，l,r放入一个集合中，用并查集来维护，并维护val[l]=s[root]-s[l],val[r]=s[root]-s[r]

若 l,r已经在同一个集合中，就直接查询val[l]-val[r]，判读与w是否相等

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define inf (1<<30)
10 #define ll long long
11 #define RG register int
12 #define rep(i,a,b)    for(RG i=a;i<=b;i++)
13 #define per(i,a,b)    for(RG i=a;i>=b;i--)
14 #define maxn 105
15 using namespace std;
16 int T,n,m;
17 int fa[maxn],val[maxn];
18 inline int read()
19 {
20     int x=0,f=1;char c=getchar();
21     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
22     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
23     return x*f;
24 }
25 
26 int find(int x)
27 {
28     if(fa[x]==x)    return x;
29     int rt=find(fa[x]);val[x]+=val[fa[x]],fa[x]=rt;return rt;
30 }
31 
32 int main()
33 {
34     int x,y,z;
35     T=read();
36     while(T--)
37     {
38         n=read(),m=read();
39         bool flg=0;
40         rep(i,0,n)    fa[i]=i,val[i]=0;
41         rep(i,1,m)
42         {
43             x=read()-1,y=read(),z=read();
44             if(find(x)!=find(y))
45                 val[fa[y]]=val[x]-val[y]-z,fa[fa[y]]=fa[x];
46             else if(val[x]-val[y]!=z)    flg=1;
47         }
48         if(!flg)    puts("true");
49         else puts("false");
50     }
51     return 0;
52 }

AC 32ms

思路二：差分约束系统

对于x1-x2=k，那么要同时满足x1-x2>=k和x1-x2<=k，即双向都建边，只是权值一正一负

然后跑SPFA判负环，如果无负环，则没有矛盾边，否则存在矛盾

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define inf (1<<30)
10 #define ll long long
11 #define RG register int
12 #define rep(i,a,b)    for(RG i=a;i<=b;i++)
13 #define per(i,a,b)    for(RG i=a;i>=b;i--)
14 #define maxn 105
15 #define maxm 1005
16 using namespace std;
17 int T,n,m,cnt;
18 int dis[maxm],vis[maxm],head[maxm];
19 struct E{
20     int v,next,val;
21 }e[maxm<<2];
22 inline int read()
23 {
24     int x=0,f=1;char c=getchar();
25     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
26     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
27     return x*f;
28 }
29 
30 inline void add(int u,int v,int val)
31 {
32     e[++cnt].v=v,e[cnt].val=val,e[cnt].next=head[u],head[u]=cnt;
33 }
34 
35 void init()
36 {
37     memset(vis,0,sizeof(vis));cnt=0;
38     memset(dis,63,sizeof(dis));dis[0]=0;
39     memset(head,0,sizeof(head));
40 }
41 
42 bool SPFA(int u)
43 {
44     vis[u]=1;
45     for(int i=head[u];i;i=e[i].next)
46     {
47         int v=e[i].v;
48         if(dis[v]>dis[u]+e[i].val)
49         {
50             dis[v]=dis[u]+e[i].val;
51             if(vis[v]||!SPFA(v))    return 0;
52         }
53     }
54     vis[u]=0;
55     return 1;
56 }
57 
58 int main()
59 {
60     int u,v,val;
61     T=read();
62     while(T--)
63     {
64         n=read(),m=read();
65         init();
66         rep(i,1,m)    u=read(),v=read(),val=read(),add(u-1,v,val),add(v,u-1,-val);
67         puts(SPFA(0)?"true":"false");
68     }
69     return 0;
70 }

AC 56ms