挖地雷

题目描述

在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

输入

N {地窖的个数}

W₁，W₂，……W_N {每个地窖中的地雷数}

X1，Y1 {表示从X1可到Y1}

X2，Y2

……

0 ，0 {表示输入结束}

输出

K1——K2——……——Kv {挖地雷的顺序}

MAX {最多挖出的地雷数}

样例输入

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

样例输出

3-4-5-6
34


这道题据说是dp，但因为本人dp很菜，于是就写了一个图论的算法。

首先数据范围很和蔼，才<=200.所以我们就可以枚举每一个点作为起始点，然后求出每一次能挖到的最多的地雷数，再尝试更新最终的答案。


具体的操作跟spfa有一点相似，就是如果从当前节点i走到下一个节点j做挖到的地雷数比以前走到j所挖到的地雷数多，就把走到j的路径更新为从i走来的。
同时，因为我们不能确定每一条路那个时候能走到头，所以要一直更新最大值Max。
最后如果从这地i个点出发挖到的地雷数Max>ans的话，就更新ans，同时更新路径。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 #include<cctype>
 9 using namespace std;
10 #define enter printf("
")
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<int> 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<int> 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 }