hdu 1224 Free DIY Tour （DAG 最长路）

　　水题一枚。

　　题目的意思是给出一个DAG，找出一条回路，路径的权值的和最大，输出最大值以及其路径。

　　构出DAG以后，spfa求最长路。

代目如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 typedef vector<int> VI;
10 const int N = 111;
11 VI rel[N];
12 int dis[N], pre[N], inter[N];
13 queue<int> Q;
14 
15 void printPath(int id, int n) {
16     if (pre[id] == id) return ;
17     printPath(pre[id], n);
18     cout << "->" << (id % n + 1);
19 }
20 
21 int main() {
22 //    freopen("in", "r", stdin);
23     int T, n, m;
24     cin >> T;
25     for (int cas = 1; cas <= T; cas++) {
26         cin >> n;
27         for (int i = 0; i < n; i++) {
28             cin >> inter[i];
29             rel[i].clear();
30             pre[i] = dis[i] = 0;
31         }
32         inter[n] = dis[n] = pre[n] = 0;
33         rel[n].clear();
34         cin >> m;
35         int u, v;
36         for (int i = 0; i < m; i++) {
37             cin >> u >> v;
38             u--, v--;
39             if (u > v) swap(u, v);
40             rel[u].push_back(v);
41 //            cout << u << ' ' << v << endl;
42         }
43         while (!Q.empty()) Q.pop();
44         Q.push(0);
45         while (!Q.empty()) {
46             int cur = Q.front();
47 //            cout << cur << endl;
48             Q.pop();
49             for (int i = 0, endi = rel[cur].size(); i < endi; i++) {
50                 int t = rel[cur][i];
51 //                cout << "t " << t << endl;
52                 if (dis[t] < dis[cur] + inter[t]) {
53                     dis[t] = dis[cur] + inter[t];
54                     pre[t] = cur;
55                     Q.push(t);
56                 }
57             }
58         }
59         printf("CASE %d#\n", cas);
60         cout << "points : " << dis[n] << endl;
61         cout << "circuit : 1";
62         printPath(n, n);
63         cout << endl;
64         if (cas < T) cout << endl;
65     }
66     return 0;
67 }

View Code

——written by Lyon