差分约束第三题
很明显的差分约束,d[y]-d[x-1]>=v d[y]-d[x-1]<=v
根据这个建图然后跑bellman-ford就可以了。
//BZOJ 1202 //by Cydiater //2016.9.2 #include <iostream> #include <cstdlib> #include <cstdio> #include <queue> #include <map> #include <cstring> #include <string> #include <algorithm> #include <iomanip> #include <cmath> #include <ctime> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) ; const int oo=0x3f3f3f3f; inline int read(){ ,f=; ;ch=getchar();} +ch-';ch=getchar();} return x*f; } ,dis[MAXN]; struct edge{ int x,y,v; }e[MAXN]; namespace solution{ inline void insert(int x,int y,int v){e[++len].x=x;e[len].y=y;e[len].v=v;} void init(){ N=read();M=read();len=; up(i,,M){ ,y=read(),v=read(); insert(x,y,-v); insert(y,x,v); } } bool Bellman_Ford(){ up(i,,N)dis[i]=oo; up(i,,N-){ ; up(j,,len)if(dis[e[j].y]>dis[e[j].x]+e[j].v){ dis[e[j].y]=dis[e[j].x]+e[j].v; flag=; } if(flag)break; } up(j,,len); ; } } int main(){ //freopen("input.in","r",stdin); using namespace solution; T=read(); while(T--){ init(); if(Bellman_Ford())puts("true"); else puts("false"); } ; }
差分约束第四题
和上一道题基本一样
//BZOJ 3436 //by Cydiater //2016.9.2 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <iomanip> #include <algorithm> #include <queue> #include <map> #include <ctime> #include <cmath> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) ; const int oo=0x3f3f3f3f; inline int read(){ ,f=; ;ch=getchar();} +ch-';ch=getchar();} return x*f; } ,dis[MAXN]; struct edge{ int x,y,v; }e[MAXN]; namespace solution{ inline void insert(int x,int y,int v){e[++len].x=x;e[len].y=y;e[len].v=v;} void init(){ N=read();M=read(); while(M--){ int flag=read(),x,y,v; ){ x=read();y=read(); insert(x,y,); insert(y,x,); } ){ x=read();y=read();v=read(); insert(x,y,-v); } ){ x=read();y=read();v=read(); insert(y,x,v); } } } bool Bellman_Ford(){ up(i,,N)dis[i]=oo; up(i,,N-){ ; up(j,,len)if(dis[e[j].y]>dis[e[j].x]+e[j].v){ dis[e[j].y]=dis[e[j].x]+e[j].v; flag=; } if(flag)break; } up(j,,len); ; } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); if(Bellman_Ford())puts("Yes"); else puts("No"); ; }