1202: [HNOI2005]狡猾的商人
- Time Limit: 10 Sec Memory Limit: 162 MB
- Submit: 4969 Solved: 2496
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=1202 ]
- 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
- HINT
- Source
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=1202 ]
- HOME https://www.lydsy.com/JudgeOnline/ Back
题解: 对于给的 i,j,w, 我们可以假设 sum[i]为前 i 天的和; 则 sum[j]-sum[i-1]==w; ==>sum[j]-sum[i-1]<=w&&sum[i-1]-sum[j]<=-w;
如果能够找到从起点到其他点的最短距离, 则为真; 如果有环的话说明存在矛盾的地方使其距离可以一直减小;
注意: 并不是任意两点都可以到达, 故分几个图寻找;
参考代码:
- #include<bits/stdc++.h>
- using namespace std;
- #define clr(a,val) memset(a,val,sizeof a)
- #define lowbit(x) x&-x
- #define PI acos(-1.0)
- typedef long long ll;
- const int INF=0x3f3f3f3f;
- int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
- return x*f;
- }
- const int maxn=1010;
- int T,n,m,x,y,z,tot,cnt[maxn];
- int head[maxn],dis[maxn],vis[maxn];
- struct Edge{
- int v,w,nxt;
- } edge[maxn<<1];
- void Init()
- {
- tot=0; clr(head,-1);
- clr(cnt,0);
- }
- void addedge(int u,int v,int w)
- {
- edge[tot].v=v;
- edge[tot].w=w;
- edge[tot].nxt=head[u];
- head[u]=tot++;
- }
- bool SPFA(int s)
- {
- queue<int> q;
- clr(dis,INF);clr(vis,0);
- dis[s]=0; vis[s]=1;
- q.push(s);
- while(!q.empty())
- {
- int u=q.front(); q.pop(); vis[u]=0;
- for(int i=head[u];~i;i=edge[i].nxt)
- {
- int v=edge[i].v;
- if(dis[v]>dis[u]+edge[i].w)
- {
- dis[v]=dis[u]+edge[i].w;
- if(!vis[v])
- {
- q.push(v);vis[v]=1;
- if(++cnt[v]>n) return false;
- }
- }
- }
- }
- return true;
- }
- int main()
- {
- T=read();
- while(T--)
- {
- Init();
- n=read();m=read();
- for(int i=1;i<=m;++i)
- {
- x=read();y=read();z=read();
- addedge(x-1,y,z);addedge(y,x-1,-z);
- }
- bool flag=true;
- for(int i=0;i<=n;++i)
- {
- if(cnt[i]) continue;
- if(!SPFA(i)) {flag=false; break;}
- }
- if(flag) puts("true");
- else puts("false");
- }
- return 0;
- }
- View Code
BZOJ[HNOI2005]狡猾的商人(差分约束)
来源: http://www.bubuko.com/infodetail-2873639.html