1262：【例9.6】挖地雷
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任意一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。
【输入】
第一行：地窖的个数；
第二行：为依次每个地窖地雷的个数；
下面若干行：
xiyi //表示从xi可到yi，xi<yi。
最后一行为"00"表示结束。
【输出】
k1−k2−…−kv //挖地雷的顺序
挖到最多的雷。
【输入样例】
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
1. #include <stdlib.h> 2. #include <cstdio> 3. #include <algorithm> 4. #include <iostream> 5. using namespace std; 6. const int M=205; 7. bool a[M][M];//是否有路 8. int w[M][4];//w[M][1]每个位置点的地雷数 w[M][2]最多地雷数 w[M][3]路径 9. int i,j,n,x,y,l,k,maxx; 10. int main() 11. { 12. cin>>n; 13. for(i=1;i<=n;i++) cin>>w[i][1]; 14. do{ 15. cin>>x>>y; 16. if(x!=0 && y!=0)a[x][y]=true; 17. }while(x!=0 || y!=0); 18. w[n][2]=w[n][1]; 19. for(i=n-1;i>=1;i--){ 20. l=0;k=0; 21. for(j=i+1;j<=n;j++) 22. if(a[i][j] && w[j][2]>l){ 23. l=w[j][2];k=j; 24. } 25. w[i][2]=w[i][1]+l; 26. w[i][3]=k; 27. } 28. k=1; 29. for(j=2;j<=n;j++) 30. if(w[j][2]>w[k][2]) k=j; 31. maxx=w[k][2]; 32. cout<<k; 33. k=w[k][3]; 34. while(k!=0){ 35. cout<<"-"<<k;k=w[k][3]; 36. } 37. cout<<endl; 38. cout<<maxx<<endl; 39. //system("pause"); 40. return 0; 41. }
