BZOJ4010:[HNOI2015] 菜肴制作

题面

错误原因

难得遇到一道题让我写错误原因。。。

错解

首先,这道题不是字典序最小,因为他从 1,2…n 依次考虑。

一开始想直接贪心遍历,从 1 号考虑,为了做 1 号,就要把它的先决菜肴都做了,于是先做价值高的先决菜肴再做第二高的,这样贪心递归下去。最后得分 10 分。。。
后来发现反例 <3,4><4,1><2,5><5,1>,
按照原来的算法,结果是 3 4 2 5 1

然而这是不对的
TM 我肯定先吃 2 再吃 3 啊。。。正解貌似是 2 3 4 5 1
错误原因在于,贪心遍历虽然保证了贪心的菜肴的最优解,但没有维护先决菜肴的最优解。换句话说,这种贪心虽然保证菜肴 1 的位置是最优的,但是它的先决菜肴的位置是没有顾及的(注意,这是在制作菜肴 1 的状态中,所以不会考虑菜肴 2,3… 要直到菜肴 1 做好了,才会考虑。而这时已经晚了,所以导致了错解)。

正解

更正刚才的算法,制作菜肴 i 的时候,考虑它的所有间接与直接的先决菜肴形成的子图,再在子图中按价值排序依次考虑。显然,麻烦,麻烦,超级麻烦。

考虑反向贪心。如果我把价值低的菜肴尽可能往后放,能否推导出全局最优解?
显然可以。既然要小 A 尽早吃到价值高的菜肴,就让他尽晚吃到价值低的菜肴。用交换法可证明。

于是,反向建图,每次找价值最小(即标号最大)的即可。

#include<bits/stdc++.h>
using namespace std;
int D;
struct graph{
    int n,m;
    int id[100001],ans[100001],ant;
    vector <int> dpc[100001];
    bool vis[100001];
    void addpath(int f,int t){dpc[f].push_back(t);
        id[t]++;
    }
    void tp(){priority_queue<int>q;
        int tot=0;
        for(int i=1;i<=n;i++)if(!id[i])q.push(i);//csh
        while(!q.empty()){int now=q.top();q.pop();
            ans[++ant]=now,tot++;
            for(int i=0;i<dpc[now].size();i++){if(!(--id[dpc[now][i]]))q.push(dpc[now][i]);
            }
        }
        if(tot<n)printf("Impossible!");
        else for(int i=ant;i>=1;i--)printf("%d",ans[i]);
        printf("\n");
    }

    void clear(){for(int i=1;i<=n;i++){dpc[i].clear();
            id[i]=0;
        }
        ant=0;
    }
};
graph g;
int main(){scanf("%d",&D);
    while(D--){scanf("%d%d",&g.n,&g.m);
        g.clear();
        for(int i=1,x,y;i<=g.m;i++){scanf("%d%d",&x,&y);
            g.addpath(y,x);
        }
        g.tp();}
    return 0;
}

额外的总结

一个 DAG 的拓扑排序的反序是它反建图的拓扑排序
相当于把所有的边反向,则关系反向,顺序反向。


 上一篇
ZROI2018.8.4 简单 DP ZROI2018.8.4 简单 DP
总结暑假的DP小练习 Exercise 1 有一排 n 个电线杆,第 i 个的高度为 。要在相邻的电线杆间造电线。每一根的代价是 。为一根电线杆增加 x 高度的代价是 $x^2
2018.10.01
下一篇 
[NOIP2013] 货车运输 [NOIP2013] 货车运输
本题关注路径上最小边权的值最大,则在图上生成一颗最大生成树,在树上跑 LCA 即可。 顺便练一下 Prim 用线段树维护最大值,树剖求 LCA. 注意非连通图的处理。 复杂度 ```cppincludein
2018.10.01
  目录