- https://www.luogu.com.cn/problem/P2196
- solution
记录挖掘最优路径
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- #define INF 2147483647
- int n,c,Ans=-1,cnt; //cnt 路径长度
- bool vis[21];
- int a[21],p[21][21],w[21],b[21]; //w[i] 记录路径, b[i] 记录答案路径
- // 路径是单向的
- bool check(int x){
- for(int i=1;i<=n;i++)
- if(p[x][i]==1)return true;
- return false;
- }
- void dfs(int x,int sum,int Depth){
- if(!check(x)){
- if(sum>Ans){
- cnt=Depth;
- Ans=sum;
- for(int i=1;i<=Depth;i++)b[i]=w[i];
- return;
- }
- else return;
- }
- for(int i=1;i<=n;i++){
- if(!vis[i]&&p[x][i]==1){
- vis[i]=1;
- w[Depth+1]=i;
- dfs(i,sum+a[i],Depth+1);
- vis[i]=0;
- }
- }
- }
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++) cin>>a[i];
- for(int i=1;i<=n-1;i++){
- for(int j=1;j<=n-i;j++){
- cin>>c;
- if(c==1)p[i][i+j]=1;
- }
- }
- for(int i=1;i<=n;i++){
- w[1]=i;
- dfs(i,a[i],1);
- }
- for(int i=1;i<=cnt;i++)cout<<b[i]<<" ";
- cout<<endl;
- cout<<Ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3415548.html