2196 挖地雷

2196 挖地雷

貌似我做过这个题，得了40分
我真的是牛逼了
路径得输出搞错，输入的方式搞成循环，就这样还能得40分
所以卡了我好多次
其实这个题真的就是很简单得图论，或者是dp之类的，但是，就是一点小小的错误，需要特别注意

#include
#include
#include
#include
#include
#define N 20
#define INF 99999999
using namespace std;
int b[N][N];
int w[N],p[N];
int f[N];// 表示挖到地雷最大数 
void print(int k) //输出挖地雷的顺序 
{if(k == 0) return;print(p[k]);if(p[k] == 0)//如果是第一个点 直接输出k 否则输出-k cout<<k<<" ";elsecout<<k<<" "; 
}
int main()
{int n;cin>>n;; for(int i=1;i<=n;i++){cin>>w[i];f[i]=w[i];}int x,y;for(int i=1;i<=n-1;i++){for(int j=i+1;j<=n;j++){cin>>b[i][j];}}		int maxx=-INF,k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(b[j][i]==1&&f[j]+w[i]>f[i])//j可以到i 且 f[j]+w[i] > f[i]{f[i]=f[j]+w[i];//保存第i个地窖起挖到的后继最大地雷数 p[i]=j;  //j 地窖是i的最优路径，也就是记录最优路径 }}if(f[i]>maxx)//计算挖到最多地雷数 {maxx=f[i];k=i;}}print(k);//输出路径 cout<<endl<<maxx<<endl;  return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！