本文主要是介绍poj 3159 （spfa差分约束最短路） poj 1201，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj 3159:
题意：
每次给出b比a多不多于c个糖果，求n最多比1多多少个糖果。
解析：
差分约束。
这个博客讲差分约束讲的比较好：
http://www.cnblogs.com/void/archive/2011/08/26/2153928.html
套个spfa。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 30000 + 10;
const int maxe = 150000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int head[maxn];
bool vis[maxn];
int dis[maxn];
int edgeNum;
int n, m;struct Edge
{int fr, to, cost;
} e[maxe];void addedge(int f, int t, int c)
{e[edgeNum].fr = head[f];e[edgeNum].to = t;e[edgeNum].cost = c;head[f] = edgeNum++;
}void spfa()
{for (int i = 1; i <= n; i++){dis[i] = inf;vis[i] = false;}stack<int> s;s.push(1);vis[1] = true;dis[1] = 0;while (!s.empty()){int cur = s.top();s.pop();for (int i = head[cur]; i != -1; i = e[i].fr){int x = e[i].to;if (dis[cur] + e[i].cost < dis[x]){dis[x] = dis[cur] + e[i].cost;if (!vis[x]){vis[x] = true;s.push(x);}}}vis[cur] = false;}
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d%d", &n, &m)){edgeNum = 0;memset(head, -1, sizeof(head));for (int i = 0; i < m; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);addedge(a, b, c);}spfa();printf("%d", dis[n]);}return 0;
}
poj 1201:
题意，解析：
而这种不等式的解法其实就是转化为图论的最小路的算法求解的。我们将上面的不等式边形后得到aj>=ai+bk正好就可以看做是从ai到aj权值是bk的一条路径最短的边。这样一来，只要依照题目的条件写出一系列这样的不等式，也就是相当于按照题意增加了一些合法的边，也就完全转化为了最短路的算法。
再看这道题，题目说[ai, bi]区间内和点集Z至少有ci个共同元素，那也就是说如果我用Si表示区间[0,i]区间内至少有多少个元素的话，那么Sbi - Sai >= ci,这样我们就构造出来了一系列边，权值为ci，但是这远远不够，因为有很多点依然没有相连接起来（也就是从起点可能根本就还没有到终点的路线）,此时，我们再看看Si的定义，也不难写出0<=Si - Si-1<=1的限制条件，虽然看上去是没有什么意义的条件，但是如果你也把它构造出一系列的边的话，这样从起点到终点的最短路也就顺理成章的出现了。
我们将上面的限制条件写为同意的形式：
Sbi - Sai >= ci
Si - Si-1 >= 0
Si-1 - Si >= -1
这样一来就构造出了三种权值的边，而最短路自然也就没问题了。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 50000 + 10;int n;
int head[maxn];
bool vis[maxn];
int dis[maxn];
int edgeNum;struct Edge
{int to, next;int val;
} e[maxn << 2];void init()
{edgeNum = 0;memset(head, -1, sizeof(head));
}void addEdge(int fr, int to, int val)
{e[edgeNum].to = to;e[edgeNum].next = head[fr];e[edgeNum].val = val;head[fr] = edgeNum++;
}void spfa(int s, int t)
{for (int i = s; i <= t; i++){dis[i] = -inf;vis[i] = false;}queue<int> q;q.push(s);vis[s] = true;dis[s] = 0;while (!q.empty()){int u = q.front();q.pop();for (int i = head[u]; i != -1; i = e[i].next){int v = e[i].to;if (dis[u] + e[i].val > dis[v]){dis[v] = dis[u] + e[i].val;if (!vis[v]){vis[v] = true;q.push(v);}}}vis[u] = false;}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d", &n)){init();int minn = inf;int maxx = -inf;for (int i = 0; i < n; i++){int fr, to, val;scanf("%d%d%d", &fr, &to, &val);addEdge(fr, to + 1, val);minn = min(minn, fr);maxx = max(maxx, to + 1);}for (int i = minn; i < maxx; i++){addEdge(i, i + 1, 0);addEdge(i + 1, i, -1);}spfa(minn, maxx);printf("%d\n", dis[maxx]);}return 0;
}
这篇关于poj 3159 （spfa差分约束最短路） poj 1201的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
