P2196 挖地雷

伊豆的舞女 · 2018-10-14 12:45:13 · 个人记录

P2196 挖地雷

思路

本题有坑，连接实际上是单向的。图是一个DAG。以每个节点为起点走最长路即可。方案记录一个pre数组，递归着输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=25,E=1<<21;
struct Way{
    int to,next;
} way[N*N];
struct Node{
    int s,val;
    Node(int a,int b){
        s=a; val=b;
    }
};
int n,a,ans,cnt,val[N],head[N];
int num,dis[N],pre[N],path[N];
bool vis[N];
queue<int>q;
void get_ans(int cur){
    if(pre[cur]) get_ans(pre[cur]);
    path[++num]=cur;
}
void spfa(int st){
    memset(dis,0,sizeof(dis));
    memset(pre,0,sizeof(pre));
    dis[st]=val[st]; q.push(st);
    while(!q.empty()){
        int cur=q.front(); q.pop();
        vis[cur]=false;
        for(int i=head[cur];i;i=way[i].next)
            if(dis[way[i].to]<dis[cur]+val[way[i].to]){
                dis[way[i].to]=dis[cur]+val[way[i].to];
                pre[way[i].to]=cur;
                if(!vis[way[i].to]){
                    vis[way[i].to]=true; q.push(way[i].to);
                }
            }
    }
    int cur=0;
    for(int i=1;i<=n;i++)
        if(dis[i]>ans){
            ans=dis[i]; cur=i;
        }
    if(cur){
        num=0; get_ans(cur);
    }
}
void add(int u,int v){
    way[++cnt].to=v;
    way[cnt].next=head[u];
    head[u]=cnt;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            scanf("%d",&a);
            if(a==1) add(i,j);
        }   
    for(int i=1;i<=n;i++)
        spfa(i);
    for(int i=1;i<=num;i++)
        printf("%d ",path[i]);
    printf("\n%d",ans);
    return 0;
}