之前做這個題使用的方法是Floyd其所有點的最長路，但是這個還可以使用SPFA來做，因為這個圖是肯定沒有正環(huán)的圖，然后把所有入讀為0的點，都一次性的加入到SPFA的隊列或者棧中，則可以求解出一個全局最大值。然后用SPFA可以加一個父親域，來回復(fù)我們獲得的路徑。
1:
2: #include <queue>
3: #include <iostream>
4: #include <string.h>
5: #include <stdio.h>
6: #include <algorithm>
7: #include <vector>
8: using namespace std;
9: #define V 30010 // vertex
10: #define E 150010 // edge
11: #define INF 0x3F3F3F3F
12:
13: struct node
14: {
15: int v, w, next;
16: }pnt[E];
17:
18: int head[V];
19: int dis[V];
20: bool vis[V];
21: int cnt[V]; // the num of the operation of push to Quque. negatvie cycle.
22: int e = 0; // the index of the edge
23: int N ; // the num of the vertex.
24: int M ; // the num of edges
25: int src, sink;
26: int father[V];
27: int ru[V];
28: void addedge(int u, int v, int w)
29: {
30: pnt[e].v = v; pnt[e].w= w;
31: pnt[e].next = head[u]; head[u] = e++;
32: }
33: void SPFA_init()
34: {
35: e=0;
36: memset(head, -1,sizeof(head));
37: memset(vis, 0 ,sizeof(vis));
38: memset(cnt, 0 ,sizeof(cnt));
39: for(int i=0; i<=N; i++) dis[i] = -1; // MODIFIED
40: memset(father, -1, sizeof(father));
41: }
42: int SPFA()
43: {
44: queue<int> Q;
45: for(int i=1; i<=N; i++)
46: {
47: src = i;
48: if(ru[i] == 0)
49: {
50: Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src];
51: }
52: }
53: while(!Q.empty())
54: {
55: int u = Q.front(); Q.pop(); vis[u] = 0;
56: for(int i=head[u]; i!=-1; i=pnt[i].next)
57: {
58: int v = pnt[i].v;
59: if( dis[v] < dis[u] + pnt[i].w ) // MODIFIED
60: {
61: dis[v] = dis[u] + pnt[i].w;
62: father[v] = u;
63: if(!vis[v]) { Q.push(v); vis[v] = 1;}
64: if( ++cnt[v] > N) return -1; // positive cycle.
65: }
66: }
67: }
68: if(dis[sink] == -1 ) return -2; // can't from src to sink.
69: return dis[sink];
70: }
71:
72: int main()
73: {
74: //freopen("1078.txt","r",stdin);
75: scanf("%d", &N);
76: int a, b;
77: vector<pair<int, int> > C;
78: memset(ru, 0 ,sizeof(ru));
79: SPFA_init();
80: for(int i=0; i<N; i++)
81: {
82: int a, b;
83: scanf("%d%d", &a, &b);
84: C.push_back(make_pair(a,b));
85: for(int i=0; i<C.size(); i++)
86: {
87: if(a<C[i].first && b> C[i].second)
88: {
89: ru[C.size()]++;
90: addedge(i+1,C.size() , 1);
91: }
92: else if(a> C[i].first && b< C[i].second)
93: {
94: ru[i+1]++;
95: addedge(C.size(), i+1,1);
96: }
97: }
98: }
99: SPFA();
100: //for(int i=1; i<=N; i++) cout<<father[i]<<" "; cout<<endl;
101: int ret =0; int idx = -1;
102: for(int i=1; i<=N; i++)
103: {
104: if(dis[i]>ret)
105: {
106: ret = dis[i];
107: idx = i;
108: }
109: }
110: if(ret == 0)
111: {
112: cout<<1<<endl;
113: cout<<1<<endl;
114: }
115: else
116: {
117: cout<<ret+1<<endl;
118: vector<int> D;
119: D.push_back(idx);
120: while(father[idx] != -1)
121: {
122: D.push_back(father[idx]);
123: idx = father[idx];
124: }
125: reverse(D.begin(), D.end());
126: for(int i=0; i<D.size(); i++) cout<<D[i]<<" ";
127: cout<<endl;
128: }
129: return 0;
130: }