1.求最小值的情况。
将关系都化成 a[ i ] - a[ j ] >= k
然后 j 向 i 建立一个价值k的有向边。
然后跑一个最长路。
例如：POJ-1201
#include<iostream> #include<cstring> #include<queue> #include<vector> #include<cassert> #include<cstdio> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 5e4 + 10; int head[N], to[N<<2], ct[N<<2], nt[N<<2]; int tot; void add(int u, int v, int w){ to[tot] = v; nt[tot] = head[u]; ct[tot] = w; head[u] = tot++; } int d[N+100]; int vis[N+100]; queue<int> q; void spfa(){ vis[0] = 1; q.push(0); while(!q.empty()){ int now = q.front(); q.pop(); vis[now] = 0; for(int i = head[now];~i; i = nt[i]){ int v = to[i]; if(d[v] < d[now] + ct[i]){ d[v] = d[now] + ct[i]; if(!vis[v]){ q.push(v); vis[v] = 1; } } } } } int main(){ memset(head, -1, sizeof head); int n, a, b, c; scanf("%d", &n); for(int i = 1; i <= n; ++i){ scanf("%d%d%d", &a, &b, &c); add(a, b+1, c); } for(int i = 0; i + 1 < N; ++i){ add(i, i+1, 0); add(i+1, i, -1); } memset(d, _inf, sizeof d); d[0] = 0; spfa(); printf("%d ", d[N-1]); return 0; }
2.求最大值的情况
将关系都转换成a[i]-a[j]<=k
然后j向i建立一个价值k的有向边。
跑一个最短路。
例如：HDU-3440
#include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 2e5 + 100; int head[1010]; int to[N], ct[N], nt[N]; int tot; void add(int u, int v, int w){ to[tot] = v; ct[tot] = w; nt[tot] = head[u]; head[u] = tot++; } void init(){ memset(head, -1, sizeof head); tot = 0; } pll p[N]; int d[1010], cnt[1010], vis[1010], n; int spfa(int s, int t){ memset(d, inf, sizeof d); memset(cnt, 0, sizeof cnt); memset(vis, 0, sizeof vis); d[s] = 0; queue<int> q; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 0; // cout << u << endl; for(int i = head[u]; ~i; i = nt[i]){ int v = to[i]; if(d[v] > d[u] + ct[i]){ d[v] = d[u] + ct[i]; if(!vis[v]){ vis[v] = 1; ++cnt[v]; if(cnt[v] > n) return -1; q.push(v); } } } } return d[t]; } int main(){ int d; int T; scanf("%d", &T); for(int _cas = 1; _cas <= T; ++_cas){ init(); /// x[i] - x[i-1] >= 1 /// x[i-1] - x[i] <= -1 scanf("%d%d", &n, &d); for(int i = 1; i < n; ++i) add(i+1, i, -1); for(int i = 1; i <= n; ++i){ scanf("%d", &p[i].fi); p[i].se = i; } sort(p+1, p+1+n); for(int i = 1; i < n; ++i){ int u = min(p[i].se, p[i+1].se); int v = u ^ p[i].se ^ p[i+1].se; /// x[v] - x[u] <= d add(u, v, d); } int s = min(p[1].se, p[n].se); int t = s ^ p[1].se ^ p[n].se; printf("Case %d: %d ", _cas,spfa(s,t)); } return 0; }
关键就是利用了三角形不等式。 因此可以用spfa来算最短/长路来解决。
需要注意的就是 可能会有一个负环/正环来无限修改答案，记得记录次数。