POJ3169 差分约束系统

http://poj.org/problem?id=3169 题意： n头牛初始排列1~n， 现在给出几个限制条件，ML个条件A,B,C表示编号为A,B的奶牛的最远距离只能是C。 MD个条件A,B,C表示A，B奶牛最近距离为C，求出编号为1与编号为n的奶牛的最远距离 如果无法满足约束条件输出$-1$,最远距离如果可以无限远输出$-2$

思路： 看到有约束条件的题基本可以想到用差分约束系统求解。 ML的条件： $B-A>=C$ MD的条件： $B-A<=C$

注意其实还有隐含条件，任意两点间的距离其实是大于等于0的（因为一开始的按序排列，题目还提到排列后两牛可能位于同一位置） 所以隐含条件: $i+1$到$i$间连一条权值为0的边，表示没有限制。 因此实际上不会出现距离无限远的情况。。（个人理解，如有错误欢迎指出，）

#include<iostream> #include<algorithm> #include<cstdio> #include<stdio.h> #include<string.h> #include<queue> #include<cmath> #include<map> #include<set> #include<vector> #include<stack> using namespace std; #define inf 1000000000000000000 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mem(a,b) memset(a,b,sizeof(a)); #define lowbit(x) x&-x; #define debugint(name,x) printf("%s: %d\n",name,x); #define debugstring(name,x) printf("%s: %s\n",name,x); typedef long long ll; typedef unsigned long long ull; const double eps = 1e-6; const int maxn = 1e5+5; const int mod = 1e9+7; 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; } int head[maxn],vis[maxn],cnt[maxn],tol; int n,ml,md; ll dis[maxn]; struct node{ int u,v,w,nxt; bool operator<(const node C)const{ return w > C.w; } }E[maxn<<1]; void init(){ mem(vis,0); mem(cnt,0); mem(head,-1); for(int i = 0; i <= n; i++) dis[i] = 1e18; tol = 0; } void addedge(int u,int v,int w){ E[tol].u = u; E[tol].v = v; E[tol].w = w; E[tol].nxt = head[u]; head[u] = tol++; } ll spfa(int s,int e){ int all = e; stack<int>st; vis[s] = true; dis[s] = 0; st.push(s); while(!st.empty()){ int u = st.top(); st.pop(); vis[u] = false; if(u == e) continue; for(int i = head[u]; ~i; i = E[i].nxt){ int v = E[i].v; int w = E[i].w; if(dis[v] > dis[u]+w){ dis[v] = dis[u]+w; if(!vis[v]){ vis[v] = true; cnt[v]++; if(cnt[v] >= all) return -1; st.push(v); } } } } return dis[e]; } int main(){ //printf("%lld\n",inf); int a,b,c; scanf("%d%d%d",&n,&ml,&md); init(); for(int i = 1; i <= ml; i++){ scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } for(int i = 1; i <= md; i++){ scanf("%d%d%d",&a,&b,&c); addedge(b,a,-c); } for(int i = 1; i <= n; i++) addedge(i+1,i,0); ll ans = spfa(1,n); if(ans == -1) puts("-1"); else if(ans == inf) puts("-2"); else printf("%lld\n",ans); }