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 累計一下前綴和，則Sum[l,r]=v等價于S[r]-S[l-1]=v。 將l-1向r連一條長度為v的邊，將r向l-1連一條長度為-v的邊。 dfs判判就可以了。 一不小心刷了rank1，IO優化真是一個好東西。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {if(head==tail) {int l=fread(buffer,1,BufferSize,stdin);tail=(head=buffer)+l;}return *head++;
}
inline int read() {int x=0,f=1;char c=Getchar();for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;for(;isdigit(c);c=Getchar()) x=x*10+c-'0';return x*f;
}
const int maxn=110;
const int maxm=2010;
int n,m,first[maxn],next[maxm],to[maxm],dis[maxm],e;
void AddEdge(int u,int v,int w) {to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e;
}
int vis[maxn],d[maxn];
int dfs(int x) {vis[x]=1;ren if(!vis[to[i]]) {d[to[i]]=d[x]+dis[i];if(!dfs(to[i])) return 0;}else if(d[to[i]]!=d[x]+dis[i]) return 0;return 1;
}
int main() {dwn(i,read(),1) {e=0;n=read()+1;m=read();memset(first,0,sizeof(first));while(m--) {int s=read(),t=read()+1,w=read();AddEdge(s,t,w);AddEdge(t,s,-w);}memset(vis,0,sizeof(vis));int ok=1;rep(i,1,n) if(!vis[i]) if(!dfs(i)) {ok=0;break;}puts(ok?"true":"false");}return 0;
}

View Code

?

轉載于:https://www.cnblogs.com/wzj-is-a-juruo/p/5010944.html

總結

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

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