浙江江能建设有限公司网站,网站建设工作室怎么接单,wordpress 域名设置,搜索引擎排名网站P2294 [HNOI2005]狡猾的商人
题意#xff1a;
你需要调查某个商人的账本#xff0c;给你n个月内#xff0c;m条账单信息#xff0c;每条账单信息为x到y月的收入或者支出多少钱#xff0c;问你根据账单信息判断这个账本是否合理
5 3
1 5 100
3 5 50
1 2 51比如样例…P2294 [HNOI2005]狡猾的商人
题意
你需要调查某个商人的账本给你n个月内m条账单信息每条账单信息为x到y月的收入或者支出多少钱问你根据账单信息判断这个账本是否合理
5 3
1 5 100
3 5 50
1 2 51比如样例 1到5月收入100,3到5月收入50,1到2月收入51 51 50 100账单不合理
题解
差分约束的题 我们用sun[i]表示前i个月的总利润 如果从第x月到第y月的利润是zz可正可负 可以得到sum[y] - sum[x-1] z(可以理解为前缀和差值) 相当于我们会得到很多这样的式子然后去验证是否合法 我们都知道差分约束是小于等于的关系那这个题怎么做
sum[y] - sum[x] z
我们可以认为是同时满足下面两个式子
sum[y] - sum[x-1] val
sum[y] - sum[x-1] val第一个式子可以转变成的形式
sum[x-1] - sum[y] -val这样就变成了差分约束的问题 连边(y,x-1),边权为-val 连边(x-1,y),边权为val 然后跑最短路去验证是否有负环…(剩下的都是差分约束的过程了)
代码
#includebits/stdc.h
using namespace std;
const int maxn1e59;
struct node{int v,w;node(int v0, int w0):v(v),w(w){};
};
vectornodeedge[maxn];
bool vis[maxn];
int dis[maxn];
int cnt[maxn];
int n,m;
bool spfa(int now)
{queueintq;dis[now]0;q.push(now);vis[now]1;while(!q.empty()){int uq.front();q.pop();vis[u]0;for(int i0;iedge[u].size();i){int vedge[u][i].v;int wedge[u][i].w;if(dis[v]dis[u]w){dis[v]dis[u]w;cnt[v]cnt[u]1;if(cnt[v]n1)return 1;if(vis[v]0){vis[v]1;q.push(v);}}}}return 0;
}
void init()
{for(int i0;in;i)edge[i].clear();memset(dis,0x3f,sizeof(dis));memset(cnt,0,sizeof(cnt));memset(vis,0,sizeof(vis));
}
int main()
{int t;cint;while(t--){cinnm;init();for(int i1;im;i){int u,v,w;cinuvw;edge[v].push_back((node){u-1,-w});edge[u-1].push_back((node){v,w});}for(int i1;in;i)edge[n1].push_back((node){i,0});if(spfa(n1))coutfalseendl;else couttrueendl;}}
/*
2
5 3
1 5 100
3 5 50
1 2 51
3 3
1 2 10
1 3 -5
3 3 -15*/
