题面描述
在一个地图上有N 个地窖(N<=200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的,且从编号小的地窖通向编号大的地窖。某人可以从任一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。
【输入格式】
N {地窖的个数}
W1,W2,……WN {每个地窖中的地雷数}
X1,Y1 {表示从X1可到Y1,保证xi<yi}
X2,Y2
……
0 ,0 {表示输入结束}
【输出格式】
K1-K2-……-Kv {挖地雷的顺序}
MAX {最多挖出的地雷数}
【输入样例】Mine.in
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
【输出样例】Mine.out
3-4-5-6
34
版本2(AC样例)
<
pre class="font-size:15 line-height:17 lang:c++ decode:true " title="挖地雷 版本2(AC样例)" >#include<bits/stdc++.h>
using namespace std;
//---------题目变量
int n,w[205],xi,yi;
//---------自用变量
//用stl也许并不是什么好主意
vector< set
vector
vector
stack
//---------主程序
int main(){
//读入部分,没什么好废话的
cin>>n;
dj.resize(n+5);//保持一点弹性的空间
opt.resize(n+5);
dp.resize(n+5);
for(int i=1;i<=n;i++){
cin>>w[i];
//cout<<"w["<<i<<"] = "<<w[i]<<endl;
}
while(true){
cin>>xi>>yi;
if(xi==0 && yi==0){
break;
}
dj[yi].insert(xi);
//stl的set遍历方法
//调试代码
set
while(j!=dj[yi].end()){
int item=*j;
j++;
}
}
//--------核心部分
for(int i=1;i<=n;i++){//从小到大遍历每个地窖
//cout<<"i = "<<i<<endl;
dp[i]=0;
if(dj[i].size()!=0){//如果有地窖通向当前地窖
//stl的set遍历方法
set<int>::iterator j=dj[i].begin();
//cout<<"dj["<<i<<"]={";
while(j!=dj[i].end()){
int item=*j;
if(dp[item]>dp[i]){
// cout<<item<<" , ";
dp[i]=dp[item];
opt[i]=item;
}
j++;
}
//cout<<"}"<<endl;
}
dp[i]+=w[i];
//cout<<"dp["<<i<<"]="<<dp[i]<<endl;
//cout<<"END"<<endl;
}
int ans=0,ansi,step=0;
for(int i=1;i<=n;i++){
if(dp[i]>ans){
ans=dp[i];
ansi=i;
}
}
while(ansi!=0){
optt.push(ansi);
ansi=opt[ansi];
step++;
}
for(int i=0;i<step-1;i++){
cout<<optt.top()<<"-";
optt.pop();
}
cout<<optt.top()<<endl;
cout<<ans<<endl;
return 0;
}
版本1(WA)
<
pre class="font-size:16 line-height:18 lang:c++ decode:true" title="挖地雷 版本1(WA)">#include<bits/stdc++.h>
using namespace std;
//---------题目变量
int n,w[205],xi,yi;
//---------自用变量
//用stl也许并不是什么好主意
vector< set
vector
vector
//---------主程序
int main(){
//读入部分,没什么好废话的
cin>>n;
dj.resize(n+5);//保持一点弹性的空间
opt.resize(n+5);
for(int i=1;i<=n;i++){
cin>>w[i];
cout<<"w["<<i<<"] = "<<w[i]<<endl;
}
while(true){
cin>>xi>>yi;
if(xi==0 && yi==0){
break;
}
dj[yi].insert(xi);
//stl的set遍历方法
//调试代码
set
cout<<"dj["<<yi<<"]={";
while(j!=dj[yi].end()){
int item=j;
cout<<item<<" , ";
j++;
}
cout<<"}"<<endl;
}
//--------核心部分
for(int i=1;i<=n;i++){//从小到大遍历每个地窖
cout<<"i = "<<i<<endl;
dp[i]=0;
if(dj[i].size()!=0){//如果有地窖通向当前地窖
//stl的set遍历方法
set
while(j!=dj[i].end()){
int item=
if(w[item]>dp[i]){
dp[i]=w[item];
}
j++;
}
}
dp[i]+=w[i];
cout<<"END"<<endl;
}
int ans=0;
for(int i=1;i<=n;i++){
if(dp[i]>ans){
ans=dp[i];
}
}
cout<<ans<<endl;
return 0;
}