题目描述
在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。
输入
N {地窖的个数}
W1，W2，……WN {每个地窖中的地雷数}
X1，Y1 {表示从X1可到Y1}
X2，Y2
……
0 ，0 {表示输入结束}
输出
K1——K2——……——Kv {挖地雷的顺序}
MAX {最多挖出的地雷数}
样例输入
65 10 20 5 4 51 21 42 43 44 54 65 60 0
样例输出
3-4-5-634 这道题据说是dp，但因为本人dp很菜，于是就写了一个图论的算法。 首先数据范围很和蔼，才<=200.所以我们就可以枚举每一个点作为起始点，然后求出每一次能挖到的最多的地雷数，再尝试更新最终的答案。 具体的操作跟spfa有一点相似，就是如果从当前节点i走到下一个节点j做挖到的地雷数比以前走到j所挖到的地雷数多，就把走到j的路径更新为从i走来的。 同时，因为我们不能确定每一条路那个时候能走到头，所以要一直更新最大值Max。 最后如果从这地i个点出发挖到的地雷数Max>ans的话，就更新ans，同时更新路径。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std;10 #define enter printf("\n")11 #define space printf(" ")12 typedef long long ll;13 const int INF = 0x3f3f3f3f;14 const int maxn = 2e2 + 5;15 inline ll read()16 {17 ll ans = 0;18 char ch = getchar(), last = ' ';19 while(!isdigit(ch)) {last = ch; ch = getchar();}20 while(isdigit(ch))21 {22 ans = ans * 10 + ch - '0'; ch = getchar(); 23 }24 if(last == '-') ans = -ans;25 return ans;26 }27 inline void write(ll x)28 {29 if(x < 0) x = -x, putchar('-');30 if(x >= 10) write(x / 10);31 putchar('0' + x % 10);32 }33 34 int n, a[maxn];35 vector v[maxn]; //存图用 36 int ans = 0, Path[maxn], pos; //ans最多地雷数，Path[]记录路径，pos路径长短 37 38 int dis[maxn], path[maxn];39 int spfa(int s, int old)40 {41 int Max = a[s], pos = 0; //注意Max的初值是原点的地雷数，因为可能只有一个点的图 42 for(int i = 1; i <= n; ++i) dis[i] = path[i] = 0;43 queue q;44 q.push(s); dis[s] = a[s];45 while(!q.empty())46 {47 int now = q.front(); q.pop();48 for(int i = 0; i < (int)v[now].size(); ++i)49 {50 if(dis[now] + a[v[now][i]] > dis[v[now][i]])51 {52 dis[v[now][i]] = dis[now] + a[v[now][i]];53 path[v[now][i]] = now; //记录路径 54 if(dis[v[now][i]] > Max) {Max = dis[v[now][i]]; pos = v[now][i];} //尝试更新Max 55 q.push(v[now][i]);56 }57 }58 }59 if(Max > ans)60 {61 ans = Max;62 int posans = 0;63 while(path[pos]) //更新路径 64 {65 Path[++posans] = pos;66 pos = path[pos]; 67 }68 Path[++posans] = s;69 return posans; //返回路径的长短 70 }71 return old; //如果更新不成功，那么路径也没有被更新，故返回原来的路径长度 72 }73 74 int main()75 {76 n = read();77 for(int i = 1; i <= n; ++i) a[i] = read();78 int x = read(), y = read();79 while(x && y)80 {81 v[x].push_back(y); //vector存图 82 x = read(); y = read();83 }84 for(int i = 1; i <= n; ++i) pos = spfa(i, pos); 85 for(int i = pos; i > 0; --i) {write(Path[i]); i == 1 ? enter : printf("-");}86 write(ans); enter;87 return 0;88 }