[LOJ2114][HNOI2015]-菜肴制作-拓扑排序+贪心
<题面>
一个蒟蒻的痛苦一天
在今天的节目集训中,麦蒙将带领大家学习9种错误的解题策略
$15\%$算法(看两个就往下走吧)
1> puts("Impossible!");
不解释(话说多测输出这个有分真是奇迹)(这个过不了样例了)
2>DFS无优化贪心法
随后,我想到,如果用dfs处理每一部分就可以将一些小的菜肴优先纳入考虑(样例也能过)
当然,这个也有错误,是贪心的目光短浅导致的,比如
1
5 4
4 1
5 1
3 4
2 5
会因为去搜了$4$而搜不到$2$,错了~
3>DFS快排法(动态申请数组内存)
这个地方主要提一点:一个巨大的数组存下一个目标会RE局部变量开不了太大(如果用全局变量,一定崩),所以先用全局暂存,再用记录的数量K开数组,但是还是WA(思路不对)(还能过样例)
int lins[P];
bool dfs(int k) {
is_v[k] = 1;
int j = 0;
for (int i = fl[k]; i != -1; i = rs[i].next) {
if ((is_v[rs[i].t]) && (!is_del[rs[i].t]))
return 1;
if (!is_v[rs[i].t]) {
lins[j] = i;
j++;
}
}
int dat[j];//在这里开了数组
for (int i = 0; i < j; i++) dat[i] = lins[i];
sort(dat + 0, dat + j, Mcmp); // cout<<"Dat:";
// for(int i=0;i<j;i++)cout<<rs[dat[i]].t<<" ";cout<<endl;
for (int i = 0; i < j; i++) { // cout<<"Willgo:"<<rs[dat[i]].t<<endl;
if (!is_v[rs[dat[i]].t]) { // puts("Cango!!");
if (dfs(rs[dat[i]].t)) {
return 1;
}
}
}
// cout<<"k<"<<k<<endl;
is_del[k] = 1;
ansadd(k); // 统计答案
return 0;
}
4>DFS判环+拓扑排序法
发现上面的问题,马上着手改,在DFS判环之后,进行拓扑,又WA了几次(诶样例什么状态)
5>DFS分离+部分图拓扑排序
其实5,6是一样的,都是把一小部分里可以拓扑的点记录,然后拓扑解决这一小块(保证了分离出来的点的优先),但是在拓扑的过程中不能确保里面具体的点的顺序,只是用的DFS还是BFS的区别
(已经不调样例了)
6>BFS分离+部分图拓扑排序
7>类迪杰斯特拉法
防止递归,用一个循环改了(但是在写的过程中真的很像迪杰),然后再拓扑。(手模样例)
8>堆优化的分离拓扑
蒟蒻听说用堆优化,于是信心满满(?)的在自己的拓扑中引进了堆,但是无力回天(方法不对啊)(样例真的水)
9>倒序思路的拓扑
这个最好想了,我直接反向建图,一般拓扑,最后反向输出就好了(样例能过)
但是这种贪心与原来的普通拓扑是一致的,有错误,不能确保编号小的菜肴优先级
这个其实很接近正解了,也许是我拓扑错了?
以下是正解:
想一下为什么建正图,直接找小编号会错。
因为我们不能首先保证小号节点优先出现,当前入度为0的点指向是不确定的
换个角度想,如果我们能确保大号节点靠后出现,小号节点自然尽量考前,这时就不必担心大号节点之下是不是更大的节点了,是不是都不影响(是就删它,不是就换一个,因为已经删了的点和现在的点有限制关系,不用担心会出错)
用堆优化这个过程,自然是大根堆了
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 101101
using namespace std;
struct SR {
int f, t, next;
} rs[N];
int ecn = 0, fl[N], deg[N];
void add(int f, int t) {
ecn++;
rs[ecn].f = f;
rs[ecn].t = t;
rs[ecn].next = fl[f];
fl[f] = ecn;
}
priority_queue<int, vector<int>, less<int> > q;
int pn, en;
int ans[N], ant = 0;
void prerun() {
ant = ecn = 0;
memset(fl, -1, sizeof fl);
memset(deg, 0, sizeof deg);
while (!q.empty()) q.pop();
memset(rs, 0, sizeof rs);
}
void addans(int k) {
ans[ant] = k;
ant++;
}
bool check() {
for (int i = 1; i <= pn; i++) {
if (deg[i] != 0)
return 1;
}
return 0;
}
void top() {
for (int i = 1; i <= pn; i++) {
if (deg[i] == 0)
q.push(i);
}
// debug(q);
while (!q.empty()) {
int f = q.top();
q.pop(); // cout<<"Got"<<f<<endl;
for (int i = fl[f]; i != -1; i = rs[i].next) {
deg[rs[i].t]--;
if (deg[rs[i].t] == 0) {
q.push(rs[i].t); // cout<<"Wii"<<rs[i].t<<endl;
}
}
addans(f);
}
if (check()) {
puts("Impossible!");
return;
}
for (int i = ant - 1; i >= 0; i--) {
printf("%d ", ans[i]);
}
puts("");
}
int main() {
int T, a, b;
cin >> T;
while (T--) {
prerun();
scanf("%d%d", &pn, &en);
for (int i = 1; i <= en; i++) {
scanf("%d%d", &a, &b);
add(b, a);
deg[a]++;
}
top();
}
return 0;
}
最新文章
- Oracle11g字符集AL32UTF8修改为ZHS16GBK详解
- Problem of saving images in WPF (RenderTargetBitmap)zz
- 深圳电信光纤用户必备:简单破解中兴ZXA10 F460光电猫,实现WIFI和自动拨号功能
- iOS开发系列—Objective-C之基础概览
- elasticsearch installation guide
- SSH登录很慢问题的解决
- JFinal开发web项目出现故障小记
- 根据父节点parentid查询节点信息
- 【Qt编程】基于Qt的词典开发系列<;十>;--国际音标的显示
- Go语言学习笔记(五) [函数]
- [ASNI C] [常用宏定义] [define技巧]
- BUILDING WITH BOOTSTRAP
- Hat’s Words HDU1247
- Easyui form 表单中的 radio 无法一开始就选中原因
- python2和3的区别 高清大图:)
- 第10章-Vue.js 项目实战
- uvaoj1586Molar mass(暴力)
- spring 和 struts 整合遇到的问题(学习中)
- php统计目录大小
- { ($0, Resolver($0.box)) }(Promise<;T>;(.pending)):闭包的定义与执行合一
热门文章
- day2-元组、字典、文件操作
- 数据结构_冒泡排序(python)
- String类型_static成员_动态内存分配_拷贝构造函数_const关键字_友元函数与友元类
- 我眼中javascript的这些年
- 一个事件一定时间内只允许点击执行一次 与 vue阻止滚动穿透
- EL bug 之 javax.el.PropertyNotFoundException: Property &#39;Sub_Token&#39; not found on type com.sunmo.stPhone.bean.User
- 83 落单的数 II
- python中关于传递参数模块argprase的一些小坑
- Activiti工作流 安装myeclipse activiti设计插件并生成数据库表
- 2019-8-31-dotnet-如何在-Mock-模拟-Func-判断调用次数