問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1201思路:
第一次寫差分約束
設s[i]表示[0...i+1]中的整數在題意要求的集合中的個數，那么根據題意有(輸入a, b, c):
s[b+1] - s[a] >= c
另外，還隱含約束條件:
1 >= s[i] - s[i-1] >=0
然后就是用Bellman-ford算法求可行解
我不理解的地方在于: Bellman-ford所求結果是可行解，如何保證是
the minimal size of set Z 或許可以參考：
http://hi.baidu.com/zf_hi/blog/item/529b830f27099aebaa645748.html代碼(轉
http://blog.163.com/lu_jian_bin2006@126/blog/static/48789281200987398473/）
1 #include<iostream>
2 #define INF 0x7fffffff
3 using namespace std;
4
5 struct {
6 int fst,sed,adj;
7 }edge[50001];
8
9 int n,mx,mn,dist[50001];
10
11 int Bellman()
12 {
13 int i,k;
14 for(i=mn;i<=mx;i++)dist[i]=0;
15
16 for(k=mn;k<=mx;k++)
17 {
18 bool flag=true;
19 for(i=1;i<=n;i++)
20 if(dist[edge[i].sed]<dist[edge[i].fst]+edge[i].adj)
21 flag=false,dist[edge[i].sed]=dist[edge[i].fst]+edge[i].adj;
22
23 for(i=mn;i<mx;i++)
24 if(dist[i]>dist[i+1])
25 dist[i+1]=dist[i],flag=false;
26
27 for(i=mx;i>mn;i--)
28 if(dist[i]-1>dist[i-1])
29 dist[i-1]=dist[i]-1,flag=false;
30
31 if(flag)break;
32 }
33 return dist[mx];
34 }
35
36 int main()
37 {
38 while(cin>>n)
39 {
40 mx=0;
41 mn=INF;
42 for(int i=1;i<=n;i++)
43 {
44 cin>>edge[i].fst>>edge[i].sed>>edge[i].adj;
45 edge[i].sed++;
46 if(edge[i].fst<mn)mn=edge[i].fst;
47 if(edge[i].sed>mx)mx=edge[i].sed;
48 }
49 cout<<Bellman()<<endl;
50 }
51 return 0;
52 }
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_E 50001
5 #define MAX_V 50002
6 #define INF 0x7FFFFFFF
7 struct Edge {
8 int from, to;
9 int cost;
10 }edges[MAX_E];
11 int n, min, max;
12 int d[MAX_V];
13
14 void
15 init()
16 {
17 int i;
18 min = INF;
19 max = 0;
20 for(i=1; i<=n; i++) {
21 scanf("%d %d %d", &edges[i].to, &edges[i].from, &edges[i].cost);
22 ++edges[i].from;
23 edges[i].cost *= (-1);
24 if(edges[i].to<min)
25 min = edges[i].to;
26 if(edges[i].from>max)
27 max = edges[i].from;
28 }
29 }
30
31 void
32 bellman_ford()
33 {
34 int i, j, flag;
35 memset(d, 0, sizeof(d)); /* the same effect to 'super souce' in CLRS */
36 for(i=min; i<=max; i++) { /* the number of verticles */
37 flag = 1;
38 /* RELAX each edge */
39 for(j=1; j<=n; j++)
40 if(d[edges[j].to] > d[edges[j].from]+edges[j].cost) {
41 d[edges[j].to] = d[edges[j].from]+edges[j].cost;
42 flag = 0;
43 }
44 for(j=min+1; j<=max; j++)
45 if(d[j] > d[j-1]+1) {
46 d[j] = d[j-1]+1;
47 flag = 0;
48 }
49 for(j=max; j>min; j--)
50 if(d[j-1] > d[j]) {
51 d[j-1] = d[j];
52 flag = 0;
53 }
54 if(flag)
55 break;
56 }
57 }
58
59 int
60 main(int argc, char **argv)
61 {
62 while(scanf("%d", &n) != EOF) {
63 init();
64 bellman_ford();
65 printf("%d\n", d[max]-d[min]); /* d[max]=0 */
66 }
67 }