当对问题建立数学模型后，发现其是一个差分方程组，那么问题可以转换为最短路问题，一下分别选用Bellmanford-SPFA解题
ZOJ2770-Burn the Linked Camp
//差分约束方程组-转换为最短路问题//d[v] <= d[u] + dis[u][v] -> d[v] - d[u] <= dis[u][v]//Time:110Ms Memory:12116#include#include #include using namespace std;#define MAXN 1005#define INF 0x3f3f3f3fstruct Edge { int u, v, w; Edge(){} Edge(int uu,int vv,int ww):u(uu),v(vv),w(ww){}}e[MAXN*MAXN];int n, m, le;int sd[MAXN]; //从1-i兵营总共最多多少人int d[MAXN];bool bellmanford(int x){ memset(d, INF, sizeof(d)); d[x] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < le; j++) { int u = e[j].u, v = e[j].v; int w = e[j].w; if (d[v] > d[u] + w) d[v] = d[u] + w; } } for (int i = 0; i < le; i++) if (d[e[i].v] > d[e[i].u] + e[i].w) return false; return true;}int main(){ //freopen("in.txt", "r", stdin); while (scanf("%d%d", &n, &m) != EOF) { int a, b, w; le = 0; for (int i = 1; i <= n; i++) { scanf("%d", &sd[i]); sd[i] += sd[i - 1]; e[le++] = Edge(i, i - 1, 0); e[le++] = Edge(i - 1, i, sd[i] - sd[i-1]); } for (int i = 1; i <= m; i++) { scanf("%d%d%d", &a, &b, &w); e[le++] = Edge(b, a - 1, -w); //e[le++] = Edge(a - 1, b, sd[b] - sd[a - 1]); } if (!bellmanford(n)) printf("Bad Estimations\n"); else printf("%d\n", -d[0]); } return 0;}
POJ1201_Intervals
//差分约束系统-SPFA//求一个集合Z中最少有多少个数//给定Z与n个区间的最小交集个数//Time:407Ms Memory:2624K#include#include #include #include #include using namespace std;#define MAX 50005#define INF 0x3f3f3f3fstruct Edge { int u, w, next; Edge(){} Edge(int uu,int ww,int nn):u(uu),w(ww),next(nn){}}e[3*MAX];int l, r, m, le;int h[MAX];int d[MAX];bool v[MAX];void spfa(int x){ memset(d, INF, sizeof(d)); memset(v, false, sizeof(v)); d[x] = 0; queue q; q.push(x); v[x] = true; while (!q.empty()) { int cur = q.front(); q.pop(); v[cur] = false; for (int i = h[cur]; i != -1; i = e[i].next) { int u = e[i].u, w = e[i].w; if (d[u] > d[cur] + w) { d[u] = d[cur] + w; if (!v[u]) { v[u] = true; q.push(u); } } } }}int main(){ memset(h, -1, sizeof(h)); scanf("%d", &m); l = INF; r = 0; for (int i = 1; i <= m; i++) { int a, b, w; scanf("%d%d%d", &a, &b, &w); r = max(b, r); l = min(a, l); e[le] = Edge(a - 1, -w, h[b]); h[b] = le++; } for (int i = l; i <= r; i++) { e[le] = Edge(i - 1, 0, h[i]); h[i] = le++; e[le] = Edge(i, 1, h[i - 1]); h[i - 1] = le++; } spfa(r); printf("%d\n", d[r] - d[l-1]); return 0;}