问题:
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 }
poj 1275 3159 1364 1716 1201 3169
这类问题，就像网络流，图论，dp，关键在列出满足的表达式，建立好数学模型，剩下的过程就很简单了。所以主要难点在于构图，从实际的描述抽象成模型。准确找到约束条件。
关于基础知识可以查看clrs 22.4节。下面只介绍我遇到的一些问题和理解。
所谓的差分约束系统，实际上指一系列的表达式，满足 形如{ xi - xj <= a}
求解实际上转化成了图论里的一个等价问题，最短路问题，实际上巧妙的利用了最短路具有的性质 di - dj <= w(j,i)
如果这样的最短路求成来了，他们的值便可以直接作为xi xj的一组可行解。
图论里求最短路，有很多方法，差分约束系统，一般利用的是单源最短路，而在单源最短路算法中，常见的是dijkstra和bellman-ford算法。这两个算法各有优劣。
dijkstra算法，效率比较高，如果用堆实现，可以达到O(vlogv+E)的复杂度,但是它只能解决正边权类型的问题，对于负边权的问题，必须采用bellman-ford算法，它的复杂度是VE.
bellman-ford算法很强大，不单可以求最短路，还可以求最长路。一般如果约束条件是 <=形式的，就标志着要求最短路，>=则要通过求最长路解决。
当然这两种约束是可以转化的，因为 xi - xj <= a实际上等价于xj- xi >= a。
一.优化途径：
1.如果改变边的松弛(relax)顺序，程序的执行顺序会有很多改观
2.当所有边都不能再松弛的时候，便可以跳出循环了，不必全部循环V-1次
这些可以通过poj1716 1201体验到
二.关于Dist[]的初始化化
1.如果将源点到各点的距离初始化为0，最终求出的最短路满足 它们之间相互最接近了
2.如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大。
这些可以从poj3169 layout 得到证实。
三.
关于dikstra算法的堆实现，有两种策略，一种是一开始把全部节点放到堆里，为每个节点维护一个在堆里的索引数组。另一种策略是当当前点被更新才放到堆里，但是要注意标记已经求得最短路的哪些点，避免重复求值。
我采用的是第一种策略，去求解的poj3159 Candies
当然还有一个优化是，如果已经找到了目标点，就可以退出了，不必全部求出最短路
四.陷阱
int a[MAX] = {INF};
注意a里面的元素只有第一个会被赋为INF,其他会被赋为0，而不是INF。
关于模型的建立，其实，很多情况下我们的 xi都是一个和式，比如从开头到现在的某个量的积累值，比如poj1716 1201中，我们要定义x[i]为点集里小于i的数的个数，则x[j] - x[i]则表示了落在线段区间[i,j]的点的个数。还有poj1364 King 也是类似，另外一些可能就是比较简单的直接的约束关系。
比较复杂的如poj1275 Cashier Employment
这个问题比较特殊，乍看其他上述问题都是寻找最小数目的点，使这些点可以覆盖线段。而这个则是找一些数目的人，而人实际上是一些线段，使这些线段可以在那些特点的总数目可以满足要求并且数目最少。关键在定义一个状态，这里如果大胆定义i时刻出纳员数目s[i]，就可以了，然后利用这个s[i]便可以找到所有的约束关系，并列出不等式，这样模型就建立好了。
这个可以参考刘汝佳的书P307，图论最短路那部分，刚好以这个问题为例，而且这个问题求的就是最长路。对于sum可以二分进行优化，不过我直接穷举也过了。
poj3159 Candies
这是我接触差分约束的第一题。设S[a]为kid a获得的candies数，则每一行代表的约束是S[b]-S[a]<=c，目标函数是使得S=S[N]-S[1]最大。
利用差分约束的思想建图，对于每一条约束，从a向b做一条长为c的边，则从1到N的最短路即为所求。由于本题c皆为非负数，所以可以用Dijkstra高效解决。
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1125思路:
题意还是蛮简单的，第一次写Floyd-Warshall算法求每对顶点间的最短距离
代码:
1 /* Floyd-Warshall algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_N 101
6 #define INF 0x7FFFFFFF
7 #define Min(a,b) ((a)<(b) ? (a) : (b))
8 #define Max(a,b) ((a)<(b) ? (b) : (a))
9 int weight[MAX_N][MAX_N];
10 int d[MAX_N][MAX_N];
11 int max[MAX_N];
12 int n;
13
14 void
15 init()
16 {
17 int i, j, cnt, t, c;
18 memset(weight, 0, sizeof(weight));
19 for(i=1; i<=n; i++) {
20 scanf("%d", &cnt);
21 for(j=0; j<cnt; j++) {
22 scanf("%d %d", &t, &c);
23 weight[i][t] = c;
24 }
25 }
26 }
27
28 void
29 floyd_warshall() /* O(n^3) */
30 {
31 int i, j, k;
32 for(i=1; i<=n; i++)
33 for(j=1; j<=n; j++)
34 d[i][j] = (i==j?0:INF);
35 for(i=1; i<=n; i++)
36 for(j=1; j<=n; j++)
37 if(weight[i][j])
38 d[i][j] = weight[i][j];
39 for(k=1; k<=n; k++) {
40 for(i=1; i<=n; i++) {
41 for(j=1; j<=n; j++) {
42 if(d[i][k]!=INF && d[k][j]!=INF)
43 d[i][j] = Min(d[i][j], d[i][k]+d[k][j]);
44 }
45 }
46 }
47 }
48
49 void
50 output()
51 {
52 int i, j, p, rt;
53 memset(max, 0, sizeof(max));
54 rt = INF;
55 for(i=1; i<=n; i++) {
56 for(j=1; j<=n; j++)
57 if(i!=j) {
58 max[i] = Max(max[i], d[i][j]);
59 }
60 if(max[i] < rt) {
61 rt = max[i];
62 p = i;
63 }
64 }
65 if(rt == INF)
66 printf("disjoint\n");
67 else
68 printf("%d %d\n", p, rt);
69 }
70
71 int
72 main(int argc, char **argv)
73 {
74 while(scanf("%d", &n)!=EOF && n) {
75 init();
76 floyd_warshall();
77 output();
78 }
79 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1511思路:
第一次写SPFA，其实是在discuss里总是看到SPFA这东东，于是今天就好奇地查了下，原来是求最短路径的快速算法
除了SPFA，这题还学到了:
1. 如何静态地建立邻接表，大开眼界，原来邻接表还可以这么建的，膜拜...
2. 求一个顶点到其他各个顶点的最短路径，显然，是单源最短路径
求其他各个顶点到某一个特定顶点的最短路径，其实也是单源最短路径，只要将原始有向图逆向即可
参考:
http://www.cnblogs.com/zhangjinglei/archive/0001/01/01/1532389.html代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 1000005
5 #define INF 0x7FFFFFFF
6 struct Edge { /* build adj-list statically */
7 int to;
8 int cost;
9 int next;
10 };
11 struct Edge edges[MAX_N], op_edges[MAX_N];
12 int assist[MAX_N], op_assist[MAX_N];
13 int mark[MAX_N], d[MAX_N];
14 int queue[MAX_N];
15 int P, Q;
16
17 void
18 init()
19 {
20 int i, f, t, c;
21 scanf("%d %d", &P, &Q);
22 memset(assist, -1, sizeof(assist));
23 memset(op_assist, -1, sizeof(op_assist));
24 for(i=0; i<Q; i++) {
25 scanf("%d %d %d", &f, &t, &c);
26 edges[i].to = t;
27 edges[i].cost = c;
28 edges[i].next = assist[f];
29 assist[f] = i;
30 /* reverse graph */
31 op_edges[i].to = f;
32 op_edges[i].cost = c;
33 op_edges[i].next = op_assist[t];
34 op_assist[t] = i;
35 }
36 }
37
38 long long
39 spfa(struct Edge *e, int *ass, int begin)
40 {
41 int i, j, head, tail, cur;
42 memset(mark, 0, sizeof(mark));
43 for(i=1; i<=P; i++)
44 d[i] = INF;
45 head = -1;
46 tail = 0;
47 d[begin] = 0;
48 mark[begin] = 1;
49 queue[tail] = begin;
50 while(head < tail) {
51 ++head;
52 cur = queue[head];
53 mark[cur] = 0;
54 for(j=ass[cur]; j!=-1; j=e[j].next) {
55 if(d[e[j].to] > d[cur]+e[j].cost) {
56 d[e[j].to] = d[cur] + e[j].cost;
57 if(!mark[e[j].to]) {
58 ++tail;
59 queue[tail] = e[j].to;
60 mark[e[j].to] = 1;
61 }
62 }
63 }
64 }
65 long long rt = 0;
66 for(i=1; i<=P; i++)
67 rt += d[i];
68 return rt;
69 }
70
71 int
72 main(int argc, char **argv)
73 {
74 int tests;
75 scanf("%d", &tests);
76 while(tests--) {
77 init();
78 printf("%lld\n", spfa(edges, assist, 1)+spfa(op_edges, op_assist, 1));
79 }
80 }
一、Bellman-Ford算法
最优性原理
它是最优性原理的直接应用，算法基于以下事实：
l 如果最短路存在，则每个顶点最多经过一次，因此不超过n-1条边；
l 长度为k的路由长度为k-1的路加一条边得到；
l 由最优性原理，只需依次考虑长度为1，2，…，k-1的最短路。
适用条件&范围
l 单源最短路径(从源点s到其它所有顶点v);
l 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
l 边权可正可负(如有负权回路输出错误提示);
l 差分约束系统（需要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，<=表示求最大值, 作为最短路。<=构图时, 有负环说明无解；求不出最短路（为Inf）为任意解。>=构图时类似）。
算法描述
l 对每条边进行|V|-1次Relax操作;
l 如果存在(u,v)∈E使得dis[u]+w<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。
时空复杂度
for i:=1 to |V|-1 do
for 每条边(u,v)∈E do Relax(u,v,w);
for每条边(u,v)∈E do
if dis[u]+w<dis[v] Then Exit(False)
算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。
改进和优化 如果循环n-1次以前已经发现不存在紧边则可以立即终止； Yen氏改进（不降低渐进复杂度）；SPFA算法
二、 SPFA算法
算法简介
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
算法流程
SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，算法大致流程是用一个队列来进行维护，即用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出队首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列 queue 和一个指示顶点是否在队列中的标记数组mark。为了方便查找某个顶点的邻接点，图采用临界表存储。
算法代码
Procedure SPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v]; relax(u,v);
if (tmp<>d[v]) and (not v in Q) then enqueue(v);
end;
end;
End;
负环处理
需要特别注意的是：仅当图不存在负权回路时，SPFA能正常工作。如果图存在负权回路，由于负权回路上的顶点无法收敛，总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。
判断负权回路的方案很多，世间流传最广、比较容易实现并且高效的方法的是记录每个结点进队次数，超过|V|次表示有负权。
三、 学以致用
POJ 1201 Intervals 差分约束系统
设S(i)为 0..i-1 中在最终序列中的的整数个数。则约束条件如下:
S(b)-S(a) >= c
0 <= S(i+1) - S(i) <= 1 <==> S(i+1)-S(i) >= 0;
S(i)-S(i+1) >= -1
注意本题要求的是最小值, 而按照>=号建图后发现图中有负环, 怎么办呢?
其实很简单, 本题求的不是最短路, 而是最长路! Bellman_ford即可!
POJ 1275 Cashier Employment 出纳员的雇佣
黑书上有详细讲解
POJ 1364 King 差分约束系统
这个题目构图之后, 只需要用bellman_ford判断是否有负圈.
构图方法:
首先进行转换:a[j]+...+a[j+m] = a[1]+...a[j+m] - (a[1]+...+a[j-1]) = sum[j+m] -
sum[j-1] >(<) ki. 差分约束只能全部是<=或者(>=).
第二步转换: sum[j+m]-sum[j-1] <= ki-1 或者 sum[j-1]-sum[j+m] <= -ki-1.
约束图构造好后就是简单的Bellman-Ford了!
POJ 1716 Integer Intervals 是1201的简单版本, 贪心算法能够得到更好的效果.
POJ 2983 Is the Information Reliable?
差分约束题, 处理一下等号的情况, 然后普通的Bellman_ford
POJ 3159 Candies 最短路径
Bellman-Ford超时, Dijkstra算法可以高效解决, SPFA(队列)居然超时...SPFA修改为堆栈实现就过了.
POJ 3169 Layout 差分约束
Bellman-Ford 和 SPFA 实现均可
POJ 3259 Wormholes 判断负权回路
TOJ 2976 Path 单纯的最短路径 可练习SPFA
ZOJ 3033 Board Games 我做的第一道Bellman-Ford题目
首先，DFS判断可达性，不可达直接输出infinity结束，可达，bellman-ford判断是否存在负环，存在输出infinity，否则，输出最短距离。
四、 参考资料
《算法导论》；《算法艺术与信息学竞赛》；《算法艺术与信息学竞赛学习指导》；NOCOW；百度百科；alpc55的小地方；highkobe；（谢谢分享）
p.s.：匆匆总结拿来分享，如有不当之处，望指出！----By Fandywang
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3463思路:
该题不会，查看别人思路后发现又是DP+Dijkstra
DP真的是相当相当地强大啊...
参考:
http://hi.baidu.com/scameeling/blog/item/c06f15f0f44e3418b07ec5fe.htmlhttp://www.cnblogs.com/zhangjinglei/archive/2009/07/31/1536160.html转载:
dp[i][1]表示到达点i最短的路有多少条，dp[i][2]表示次短的条数
dist[i][1]表示到达点i最短路的长度,dist[i][2].........................
初始化为dist[st][1]=0 其他为max_int dp[st][1]=1 其他为0
用v去松驰u时有四种情况 (设当前dist[v][cas])
情况1：dist[v][cas]+w(v,u)<dist[u][1]，找到一个更短的距离，则把原来最短的距离作为次短的距离，同时更新最短的.即
dist[u][2]=dist[u][1]
dist[u][1]=dist[v][cas]+w(v,u);
dp[u][2]=dp[u][1]
dp[u][1]=dp[v][cas]，
把Node(dist[u][1],u,1)和Node(dist[u][2],u,2)放入队列
情况2：dist[v][cas]+w(v,u)==dist[u][1]，找到一条新的相同距离的最短路，则dp[u][1]+=dp[v][cas],其他不用更新,也不入队
情况3：dist[v][cas]+w(v,u)<dist[u][2]，不可以更新最短距离，但可以更新次短的，则更新dist[u][2]和dp[u][2]
dist[u][2]=dist[v][cas]+w(v,u);
dp[u][2]=dp[v][cas];
把Node(dist[u][2],u,2)放入队列
情况4：dist[v][cas]+w(v,u)==dist[u][2] 找到一条新的相同距离的次短路,则dp[u][2]+=dp[v][cas],其他不更新。
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 1001
5 #define INF 0x7FFFFFFF
6 int d[MAX_N][2], in[MAX_N][2], cnt[MAX_N][2];
7 int n, m, from, to;
8 struct Node {
9 int target, cost;
10 struct Node *next;
11 };
12 struct Node *nodes[MAX_N]; /* adj list: there may be different roads between city A and city B */
13
14 void
15 init()
16 {
17 int i, f, t, c;
18 struct Node *fresh;
19 memset(nodes, 0, sizeof(nodes));
20 scanf("%d %d", &n, &m);
21 for(i=0; i<m; i++) {
22 scanf("%d %d %d", &f, &t, &c);
23 fresh = (struct Node *)malloc(sizeof(struct Node));
24 fresh->target = t;
25 fresh->cost = c;
26 fresh->next = nodes[f];
27 nodes[f] = fresh;
28 }
29 scanf("%d %d", &from, &to);
30 }
31
32 void
33 dijkstra()
34 {
35 int i, j, k, p, min, v, cur;
36 struct Node *tmp;
37 memset(in, 0, sizeof(in));
38 memset(cnt, 0, sizeof(cnt));
39 /* d[i][0]: minimum path, d[i][1]: second minimum path */
40 for(i=1; i<=n; i++)
41 d[i][0] = d[i][1] = INF;
42 d[from][0] = 0;
43 cnt[from][0] = 1;
44 for(i=1; i<=2*n; i++) { /* each vertex has two chance to relax */
45 min = INF;
46 p = -1;
47 for(j=1; j<=n; j++) {
48 if(!in[j][0] && d[j][0]<min) {
49 min = d[j][0];
50 p = j;
51 k = 0;
52 } else if(!in[j][1] && d[j][1]<min) {
53 min = d[j][1];
54 p = j;
55 k = 1;
56 }
57 }
58 if(p == -1)
59 break;
60 in[p][k] = 1;
61 tmp = nodes[p];
62 while(tmp != NULL) { /* Relax */
63 v = tmp->target;
64 cur = d[p][k] + tmp->cost;
65 if(cur < d[v][0]) {
66 d[v][1] = d[v][0];
67 cnt[v][1] = cnt[v][0];
68 d[v][0] = cur;
69 cnt[v][0] = cnt[p][k];
70 } else if(cur == d[v][0]) {
71 cnt[v][0] += cnt[p][k];
72 } else if(cur < d[v][1]) {
73 d[v][1] = cur;
74 cnt[v][1] = cnt[p][k];
75 } else if(cur == d[v][1]) {
76 cnt[v][1] += cnt[p][k];
77 }
78 tmp = tmp->next;
79 }
80 }
81 }
82
83 int
84 main(int argc, char **argv)
85 {
86 int tests, rt;
87 scanf("%d", &tests);
88 while(tests--) {
89 init();
90 dijkstra();
91 rt = cnt[to][0];
92 if(d[to][0]+1 == d[to][1])
93 rt += cnt[to][1];
94 printf("%d\n", rt);
95 }
96 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2263思路:
这题，我自己的想法是更像DP，设源点是source，d[i]表示从source到顶点i的每条路径中的最小值的最大值，即该题要求的结果
d[i] = max (d[i], min(d[k], adj[k][i]))，其中顶点k是从source到顶点i的路径中顶点i的前趋
具体编程的话，更像是Dijkstra的方式，只不过这里所有的顶点都必须更新
另外，这题还用到了字符串哈希，来将每个顶点用一个整数表示
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 201
5 #define MAX_LEN 31
6 #define INF 0x7FFFFFFF
7 #define HASH_LEN 19999
8 #define Min(a, b) ((a)<(b) ? (a) : (b))
9 #define Max(a, b) ((a)<(b) ? (b) : (a))
10 int n, r, hash_val;
11 int from, to, adj[MAX_N][MAX_N];
12 int d[MAX_N], in[MAX_N];
13 struct City{
14 char name[MAX_LEN];
15 int num;
16 } cities[MAX_N];
17 struct Node {
18 int index;
19 struct Node *next;
20 };
21 struct Node *hash[HASH_LEN] = {NULL};
22
23 int ELFHash(char *str)
24 {
25 unsigned long t, hash = 0;
26 while(*str) {
27 hash = (hash<<4) + (*str++);
28 if((t = hash&0xF0000000L))
29 hash ^= t>>24;
30 hash &= ~t;
31 }
32 return (hash & 0x7FFFFFFF)%HASH_LEN;
33 }
34
35 void
36 insert(int index)
37 {
38 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
39 node->index = index;
40 node->next = hash[hash_val];
41 hash[hash_val] = node;
42 }
43
44 int
45 search(char *str)
46 {
47 struct Node *node = hash[hash_val];
48 while(node != NULL) {
49 if(strcmp(str, cities[node->index].name) == 0)
50 return cities[node->index].num;
51 node = node->next;
52 }
53 return -1;
54 }
55
56 void
57 init()
58 {
59 int i, j, mark, f, t, c;
60 char str[MAX_LEN];
61 memset(hash, 0, sizeof(hash));
62 memset(adj, 0, sizeof(adj));
63 for(j=0, mark=1, i=0; i<r; i++) {
64 scanf("%s", cities[j].name);
65 hash_val = ELFHash(cities[j].name);
66 if((f=search(cities[j].name)) == -1) {
67 insert(j);
68 cities[j].num = mark++;
69 f = cities[j].num;
70 j++;
71 }
72 scanf("%s", cities[j].name);
73 hash_val = ELFHash(cities[j].name);
74 if((t=search(cities[j].name)) == -1) {
75 insert(j);
76 cities[j].num = mark++;
77 t = cities[j].num;
78 j++;
79 }
80 scanf("%d", &c);
81 if(adj[f][t] < c)
82 adj[f][t] = adj[t][f] = c;
83 }
84 scanf("%s", str);
85 hash_val = ELFHash(str);
86 from = search(str);
87 scanf("%s", str);
88 hash_val = ELFHash(str);
89 to = search(str);
90 }
91
92 void
93 solve()
94 {
95 int i, j, k, tmp;
96 memset(in, 0, sizeof(in));
97 for(i=1; i<=n; i++)
98 d[i] = 0;
99 d[from] = INF;
100 in[from] = 1;
101 for(i=1; i<=n; i++) {
102 if(adj[from][i])
103 d[i] = adj[from][i];
104 }
105
106 k = n-1;
107 while(k > 0) {
108 for(i=1; i<=n; i++) {
109 if(!in[i] && d[i]!=0) {
110 for(j=1; j<=n; j++) {
111 if(adj[i][j]) {
112 tmp = Min(d[i], adj[i][j]);
113 d[j] = Max(d[j], tmp);
114 }
115 }
116 in[i] = 1;
117 --k;
118 }
119 }
120 }
121 }
122
123 int
124 main(int argc, char **argv)
125 {
126 int tests = 0;
127 while(scanf("%d %d", &n, &r) != EOF) {
128 if(n==0 && r==0)
129 break;
130 init();
131 solve();
132 printf("Scenario #%d\n%d tons\n\n", ++tests, d[to]);
133 }
134 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1158思路:
按照Dijkstra算法的思路来求解，关键是每确定一个顶点的更新操作需要考虑因为交通灯导致的等待时间
算法本身并不复杂，自己写出来以后一直TLE...
分析之后的原因是计算两个junctions之间等待交通灯一致所需要等待的时间这一代码块会导致超时
我自己的naive想法是依次递增等待时间(加1)，然后检查交通灯是否一致
去图书馆看书的时候突然想到可以取模，但本质还是递增检查，结果还是TLE
参考了别人代码后发现，在取模之后，就可以分情况讨论，直接得出等待时间
参考:
http://blog.sina.com.cn/s/blog_5c95cb070100cxtr.html代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 301
5 #define INF 0x7FFFFFFF
6 #define Min(a, b) ((a)<(b) ? (a) : (b))
7 struct Junction {
8 int color; /* 0: blue, 1: purple */
9 int left;
10 int dur[2]; /* 0: blue, 1: purple */
11 }junctions[MAX_N];
12 int from, to;
13 int n, m;
14 int adj[MAX_N][MAX_N], d[MAX_N], in[MAX_N];
15
16 void
17 find_color(int index, int past, int *color, int *left) /* past: the time past from 0 */
18 {
19 int i;
20 if(past < junctions[index].left) {
21 *color = junctions[index].color;
22 *left = junctions[index].left - past;
23 return;
24 }
25 past -= junctions[index].left;
26 past = past%(junctions[index].dur[0] + junctions[index].dur[1]);
27 if(junctions[index].color == 0) {
28 if(past<junctions[index].dur[1]) {
29 *color = 1;
30 *left = junctions[index].dur[1] - past;
31 } else {
32 *color = 0;
33 *left = junctions[index].dur[0] + junctions[index].dur[1] - past;
34 }
35 }
36 else {
37 if(past<junctions[index].dur[0]) {
38 *color = 0;
39 *left = junctions[index].dur[0] - past;
40 } else {
41 *color = 1;
42 *left = junctions[index].dur[0] + junctions[index].dur[1] - past;
43 }
44 }
45 }
46
47 void
48 update(int index, int bt) /* bt: the beginning time for current update */
49 {
50 int i, tm, color_a, color_b, left_a, left_b;
51 for(i=1; i<=n; i++) {
52 if(!in[i] && adj[index][i] && d[i]>bt+adj[index][i]) {
53 find_color(index, bt, &color_a, &left_a);
54 find_color(i, bt, &color_b, &left_b);
55 if(color_a == color_b)
56 tm = 0;
57 else {
58 if(left_a != left_b)
59 tm = Min(left_a, left_b);
60 else {
61 if(color_a == 0) {
62 if(junctions[index].dur[1] != junctions[i].dur[0])
63 tm = left_a + Min(junctions[index].dur[1], junctions[i].dur[0]);
64 else if(junctions[index].dur[0] != junctions[i].dur[1])
65 tm = left_a + junctions[index].dur[1] + Min(junctions[index].dur[0], junctions[i].dur[1]);
66 else
67 tm = INF;
68 }
69 else {
70 if(junctions[index].dur[0] != junctions[i].dur[1])
71 tm = left_a + Min(junctions[index].dur[0], junctions[i].dur[1]);
72 else if(junctions[index].dur[1] != junctions[i].dur[0])
73 tm = left_a + junctions[index].dur[0] + Min(junctions[index].dur[1], junctions[i].dur[0]);
74 else
75 tm = INF;
76 }
77 }
78 }
79 if(tm!=INF && d[i]>d[index]+adj[index][i]+tm)
80 d[i] = d[index]+adj[index][i]+tm;
81 }
82 }
83 }
84
85 void
86 dijkstra(int source)
87 {
88 int i, j, k, cur;
89 memset(in, 0, sizeof(in));
90 for(i=1; i<=n; i++)
91 d[i] = INF;
92 in[source] = 1;
93 d[source] = 0;
94 update(source, 0);
95 for(i=2; i<=n; i++) {
96 cur = INF;
97 for(j=1; j<=n; j++)
98 if(!in[j] && d[j]<=cur) {
99 k = j;
100 cur = d[j];
101 }
102 in[k] = 1;
103 if(k == to)
104 break;
105 if(d[k] != INF)
106 update(k, d[k]);
107 }
108 }
109
110 void
111 input_init()
112 {
113 int i, f, t, c;
114 char tmp[2];
115 scanf("%d %d", &n, &m);
116 for(i=1; i<=n; i++) {
117 scanf("%s %d %d %d", tmp, &junctions[i].left, &(junctions[i].dur[0]), &(junctions[i].dur[1]));
118 junctions[i].color = (tmp[0]=='B' ? 0 : 1);
119 }
120 memset(adj, 0, sizeof(adj));
121 for(i=0; i<m; i++) {
122 scanf("%d %d %d", &f, &t, &c);
123 adj[f][t] = c;
124 adj[t][f] = c;
125 }
126 }
127
128 int
129 main(int argc, char **argv)
130 {
131 while(scanf("%d %d", &from, &to) != EOF) {
132 input_init();
133 dijkstra(from);
134 printf("%d\n", d[to]==INF ? 0 : d[to]);
135 }
136 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1828思路:
按照坐标从上到下、从左到右排序
首先想到的是O(n^2)的算法，时间需要1600+MS
然后，发现其实在排序之后只要从后向前扫描一遍即可得出结果
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 50001
5 int n;
6 struct Point {
7 int x, y;
8 }points[MAX_LEN];
9
10 int
11 compare(const void *arg1, const void *arg2)
12 {
13 struct Point *a = (struct Point *)arg1;
14 struct Point *b = (struct Point *)arg2;
15 if(a->x == b->x)
16 return a->y - b->y;
17 return a->x - b->x;
18 }
19
20 int
21 main(int argc, char **argv)
22 {
23 int i, j, cnt, ymax;
24 while(scanf("%d", &n)!=EOF && n) {
25 for(i=0; i<n; i++)
26 scanf("%d %d", &points[i].x, &points[i].y);
27 qsort(points, n, sizeof(struct Point), compare);
28 /* O(n^2) AC 1600+MS
29 cnt = 0;
30 for(i=0; i<n; i++) {
31 for(j=i+1; j<n; j++) {
32 if(points[j].y >= points[i].y)
33 break;
34 }
35 if(j == n)
36 ++cnt;
37 }
38 */
39 /* O(nlgn) AC 235MS */
40 cnt = 1;
41 ymax = points[n-1].y;
42 for(i=n-2; i>=0; i--) {
43 if(ymax < points[i].y) {
44 ++cnt;
45 ymax = points[i].y;
46 }
47 }
48 printf("%d\n", cnt);
49 }
50 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167参考:
http://angels1.0.blog.163.com/blog/static/84580504200892072639857/思路:
这题比我想象的要难好多，可以说，在看了别人AC代码之后，发现已经超越了我目前的能力
我自己的想法很简单，暴力搜索每条可能的路线，枚举每条路线的前两个点，DFS，结果始终是TLE
正确思路:
特别需要注意理解清楚题意：
Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour.
如果找出前两个点，那么这条路径上的后续点也必须存在
对输入进行预处理，找出所有可能的路径，并且按照路径中点的个数的多少降序排列（因为题意要求使得路线尽可能的少，所以首先搜索包含点个数最多的路径）
另外，还有一些简单的数学推导:
start - interval < 0 (1) [点start之前不能存在其他点]
59 - interval > start (2)
根据(1), (1)我们就可以知道start <= 29
代码中还有一处非常重要的减枝(不剪就会TLE)：
只写 r_cnt+1>=min还是会TLE
1 /* important pruning */
2 if(r_cnt+1+(left-routes[k].stops)/routes[k].stops >= min)
3 return;
4
代码(TLE):
1 void
2 dfs(int begin, int cur_routes)
3 {
4 int i, j, k, diff, cur, next=-1;
5 if(cur_routes>MAX_ROUTES || cur_routes>=min)
6 return;
7 if(begin == -1) {
8 min = cur_routes;
9 return;
10 }
11 --tm[begin];
12 cur = begin;
13 for(i=cur+1; i<MAX_T; i++) {
14 if(tm[i]) {
15 diff = i - begin;
16 /* check */
17 for(j=i; j<MAX_T; j+=diff)
18 if(!tm[j])
19 break;
20 if(j<MAX_T)
21 continue;
22
23 for(j=i; tm[j]&&j<MAX_T; j+=diff)
24 --tm[j];
25 for(k=begin+1; k<MAX_T/2; k++)
26 if(tm[k] && next==-1)
27 next = k;
28 dfs(next, cur_routes+1);
29 for(j=i; j<MAX_T; j+=diff)
30 ++tm[j];
31 cur = i;
32 }
33 }
34 ++tm[begin];
35 }
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_R 910
5 #define MAX_T 60
6 #define MAX_RT 17
7 struct Route {
8 int begin;
9 int interval;
10 int stops;
11 } routes[MAX_R];
12 int cnt, left, n, min, tm[MAX_T];
13
14 int
15 compare(const void *arg1, const void *arg2)
16 {
17 return ((struct Route *)arg2)->stops - ((struct Route *)arg1)->stops;
18 }
19
20 int
21 check(int begin, int interval)
22 {
23 int i;
24 for(i=begin; i<MAX_T; i+=interval)
25 if(!tm[i])
26 return 0;
27 return 1;
28 }
29
30 void
31 init()
32 {
33 int i, j, tmp;
34 min = MAX_RT + 1;
35 cnt = 0;
36 left = n;
37 memset(tm, 0, sizeof(tm));
38 for(i=0; i<n; i++) {
39 scanf("%d", &tmp);
40 ++tm[tmp];
41 }
42 for(i=0; i<29; i++) { /* 0<=begin<=29 */
43 if(tm[i]) {
44 for(j=i+1; j<59-i; j++)
45 if(check(i, j)) {
46 routes[cnt].begin = i;
47 routes[cnt].interval = j;
48 routes[cnt++].stops = 1 + (59-i)/j;
49 }
50 }
51 }
52 qsort(routes, cnt, sizeof(struct Route), compare); /* descend order */
53 }
54
55 void
56 dfs(int index, int r_cnt)
57 {
58 int i, k, j;
59 if(left == 0) {
60 min = min<r_cnt ? min : r_cnt;
61 return;
62 }
63 for(i=index; i<cnt&&routes[i].stops>left; i++);
64 for(k=i; k<cnt; k++) {
65 /* important pruning */
66 if(r_cnt+1+(left-routes[k].stops)/routes[k].stops >= min)
67 return;
68
69 if(check(routes[k].begin, routes[k].interval)) {
70 for(j=routes[k].begin; j<MAX_T; j+=routes[k].interval) {
71 --tm[j];
72 --left;
73 }
74 dfs(k, r_cnt+1);
75 for(j=routes[k].begin; j<MAX_T; j+=routes[k].interval) {
76 ++tm[j];
77 ++left;
78 }
79 }
80 }
81 }
82
83 int
84 main(int argc, char **argv)
85 {
86 while(scanf("%d", &n) != EOF) {
87 init();
88 dfs(0, 0);
89 printf("%d\n", min);
90 }
91 }