题解 P1854 【花店橱窗布置】

asuldb · 2018-02-09 20:56:37 · 题解

//楼下全是dp，那么来个最长路做法 
//可以将这个看成一个以花为横，瓶为纵的表格从下向上找一条路径，上一排的位置必须小于下一排
//那么我们就可以连边去跑最长路了
//同时我们注意到需要记录路径
//那么这里就选dij好了（因为其他的不会记路径啊） 
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#pragma GCC optimize(3)
#define re register
#define maxn 10001
#define maxw 800000
#define inf -99999999
using namespace std;
struct node
{
    int v,w,nxt;
}e[maxw];
int f,v,ans,num=1,end;
int head[maxn],d[maxn],r[maxn];
int a[101][101];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,less<pii> > q;
inline int read()
{
    char c=getchar();
    int x=0;
    int r=1;
    while(c<'0'||c>'9') 
    {
        if(c=='-') r=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-48;
        c=getchar();
    }
    return r*x;
}
inline void add_edge(int x,int y,int z)
{
    e[num].v=y;
    e[num].w=z;
    e[num].nxt=head[x];
    head[x]=num++;
}
inline void dijkstra(int s)
{
    for(re int i=1;i<=f*v;i++)
      d[i]=inf;
    d[s]=0;
    q.push(make_pair(d[s],s));
    while(q.size())
    {
        pii mid=q.top();
        q.pop();
        int k=mid.second;
        for(re int i=head[k];i;i=e[i].nxt)
        if(d[e[i].v]<d[k]+e[i].w)
        {
            d[e[i].v]=d[k]+e[i].w;
            q.push(make_pair(d[e[i].v],e[i].v));//很常规的松弛操作 
            r[e[i].v]=k;//存一下前驱结点，用来找路径 
        }
    }
}
void dfs(int i)
{
    if(i!=0) dfs(r[i]);
    if(i!=0) cout<<i%v<<" ";//dfs找出路径，再将点还原成二维 
}
int main()
{
    f=read();
    v=read();
    for(re int i=1;i<=f;i++)
    for(re int j=1;j<=v;j++)
    a[i][j]=read();
    for(re int i=1;i<=v;i++)
      add_edge(0,i,a[1][i]);//我们把0作为起点，把第一列的所有点与0相连 
    for(re int i=2;i<=f;i++)
    for(re int k=1;k<=v;k++)
    for(re int j=k+1;j<=v;j++)
      add_edge((i-2)*v+k,(i-1)*v+j,a[i][j]);//把点的坐标压成一维 
      //连边，需要注意的是上一行点的横坐标要小于下一行的 
    dijkstra(0);
    ans=inf;
    for(re int i=1;i<=v;i++)
    if(ans<d[(f-1)*v+i])//从最后一行找最长路 
    {
        ans=d[(f-1)*v+i];
        end=(f-1)*v+i;
    }
    cout<<ans<<endl;
    dfs(r[end]);
    end%=v;
    if(end==0) end=v;
    cout<<end<<endl;
    return 0;
}