[bzoj1202][HNOI2005]狡猾的商人
t组数据。每次给你n，m，表示有n和m个条件，表示有n个整数，然后给出m个条件，每个条件有a,b,w，表示第a个到第b个的数的和w，你要判断每组数据的条件是否合法。t,n<=100,m<=1000
题解:把数组前缀和一下，然后对于每个条件,从a-1向b连权值为w的边，并且建出反边。然后求一下有没有两个点之间存在两种不同距离的路径就好啦。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; inline 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; } struct edge{int next,to,w;}e[2005]; int q[101],top,tail,n,m,d[101],cnt,head[101]; bool b[101],yes; inline void ins(int f,int t,int w){e[++cnt].next=head[f];head[f]=cnt;e[cnt].to=t;e[cnt].w=w;} void solve(int from) { b[from]=1;d[from]=0;top=tail=0;q[++top]=from; while(top!=tail) { int u=q[++tail]; for(int i=head[u];i;i=e[i].next) { if(!b[e[i].to]){b[e[i].to]=1;d[e[i].to]=d[u]+e[i].w;q[++top]=e[i].to;} else if(d[e[i].to]!=d[u]+e[i].w){yes=false;return;} } } } int main() { int t=read(); while(t--) { n=read();m=read();cnt=0;yes=true; memset(b,0,sizeof(b));memset(head,0,sizeof(head)); for(int i=1;i<=m;i++) {int u=read(),v=read(),w=read();ins(u-1,v,w);ins(v,u-1,-w);} for(int i=0;i<=n&&yes;i++)if(!b[i]&&head[i])solve(i); puts(yes?"true":"false"); } return 0; }优质内容筛选与推荐>>
1、WCF随笔3----消息编码器
2、不要伤害指针（7）--指针类型转换
3、C#中字符“.NET研究”串的内存分配与驻留池
4、2018/3/15-2018/3/21
5、Java中的引用类型