第一行:三个整数N,ML,MDN,M_L,M_DN,ML,MD,用空格分隔。 第2…ML+12 \dots M_L+12…ML+1行:每行三个整数A,B,D,用空格分隔,表示PA−PB≤DP_A-P_B \leq DPA−PB≤D。 第ML+2…ML+MD+1M_L+2 \dots M_L+M_D+1ML+2…ML+MD+1行:每行三个整数A,B,D,用空格分隔,表示PA−PB≥DP_A-P_B \geq DPA−PB≥D。 保证1≤A<B≤N,1 \le A<B \le N,1≤A<B≤N,1≤D≤1061 \leq D \leq10^61≤D≤106.
一行,一个整数。如果没有合法方案,输出-1\texttt{-1}-1.如果有合法方案,但1号奶牛可以与N号奶牛相距无穷远,输出-2\texttt{-2}-2.否则,输出1号奶牛与N号奶牛间的最大距离。示例1
4 2 1 1 3 10 2 4 20 2 3 3
27
这四头牛分别位于0,7,10,27。
对于全部数据,2≤N≤1000,1≤ML,MD≤104,1≤L,D≤1062 \leq N \leq 1000,1 \leq M_L,M_D \leq 10^4,1 \leq L,D \leq 10^62≤N≤1000,1≤ML,MD≤104,1≤L,D≤106。
差分约束的最大值问题
就得想到每个最大值的上界最小。
所以公式就是a <= b + d。add(a,b,d)
第一问问能不能实现,就是在判断有没有负环,将所有点放入队列中去判断有没有环就可以了
第二问问是不是无穷远,只用从 1 开始跑 spfa 差分约束就可以了。
第三问同理
//-------------------------代码---------------------------- //#define int ll const int N = 1e5+10; int n,ml,md; V<pii>e[N]; int dist[N],cnt[N]; bool vis[N]; bool spfa(int size) { ms(dist,0x3f); ms(vis,0); queue<int> q; fo(i,1,size) { q.push(i); dist[i] = 0; vis[i] = 1; } while(q.size()) { auto tmp = q.front();q.pop(); vis[tmp] = 0; for(auto it:e[tmp]) { int j = it.first,w = it.second; if(dist[j] > dist[tmp] + w) { dist[j] = dist[tmp] + w; cnt[j] = cnt[tmp] + 1; if(cnt[j] == n) return 1; if(!vis[j]) { vis[j] = 1; q.push(j); } } } } return 0; } void solve() { cin>>n>>ml>>md; fo(i,1,ml) { int a,b,c;cin>>a>>b>>c; if(a > b) swap(a,b); e[a].pb({b,c}); } fo(i,1,md) { int a,b,c;cin>>a>>b>>c; if(a > b) swap(a,b); e[b].pb({a,-c}); } if(spfa(n)) cout<<-1<<endl; else { spfa(1); if(dist[n] == inf) cout<<-2<<endl; else cout<<dist[n]<<endl; } } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) // int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------