Hdoj5195DZYLovesTopologicalSorting【拓扑】+【线段树】

作者:网络    软件教程库   2020-05-11

dzy loves topological sorting

time limit: 4000/2000 ms (java/others) memory limit: 131072/131072 k (java/others)
total submission(s): 922 accepted submission(s): 269

problem description
a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u→v) from vertex u to vertex v, u comes before v in the ordering.
now, dzy has a directed acyclic graph(dag). you should find the lexicographically largest topological ordering after erasing at most k edges from the graph.

input
the input consists several test cases. (testcase≤5)
the first line, three integers n,m,k(1≤n,m≤105,0≤k≤m).
each of the next m lines has two integers: u,v(u≠v,1≤u,v≤n), representing a direct edge(u→v).

output
for each test case, output the lexicographically largest topological ordering.

sample input
5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3

sample output
5 3 1 2 4
1 3 2

hint
case 1.
erase the edge (2-3),(4-5).
and the lexicographically largest topological ordering is (5,3,1,2,4).

题意:给你n条边,删去不多于k条边,使输出的字典序最大!!
策略:我们每次都找小于等于当前k的较大的数输出就好了,
需明白:1,每减去一个入度都是减去一条边。
2:找到一个点之后,一定要将对应点的入度变为最大值,以防后面还有可能被找到。
代码:

#include cstdio
#include cstring
#include vector
#include iostream
#include algorithm
const int m = 1e5+5;
const int inf = 0x3f3f3f3f;
using namespace std;

int c[m2], in[m];
vectorint  m[m];
vectorint  ans;
int n, mm, k;

void update(int p, int x, int l, int r, int pos){
    if(l == r){
        c[pos] = x; return ;
    }
    int mid = (l+r)1;
    if(p = mid) update(p, x, l, mid, pos1); //left和right都是代表的对应的点。
    else update(p, x, mid+1, r, pos1|1);
    c[pos] = min(c[pos1], c[pos1|1]);
}

int query(int l, int r, int pos){
    if(l == r) return l;
    int mid = (l+r)1;
    if(c[pos1|1] = k) return query(mid+1, r, pos1|1);//每次都是尽量选比较大的点
    return query(l, mid,pos1);
}

void topo(){
    for(int i = 0; i  n; ++ i){
        int temp = query(1, n, 1);
        k -= in[temp];//表示去掉几个点
        ans.push_back(temp);
        update(temp, inf, 1, n, 1); //找到后就要更新
        in[temp] = inf; //一定要变为正无穷
        for(int i = 0; i  m[temp].size(); ++ i){
            int v = m[temp][i];
            --in[v]; 
            update(v, in[v], 1, n, 1);
        }

    }
}

int main(){
    while(scanf("%d%d%d", n, mm, k) == 3){
        for(int i = 0; i = n; ++ i){
            m[i].clear(); in[i] = 0;
        }
        int u, v;
        for(int i = 0; i  mm; ++ i){
            scanf("%d%d", u, v);
            ++in[v];
            m[u].push_back(v);
        }
        for(int i = 1; i = n; ++ i){
            update(i, in[i], 1, n, 1);
        }
        ans.clear();
        topo();
        printf("%d", ans[0]);
        for(int i = 1; i  n; ++ i)
            printf(" %d", ans[i]);
        printf("\n");
    }
    return 0;
} 

hdoj 5195 dzy loves topological sorting 【拓扑】+【线段树】

原文地址:http://blog.csdn.net/shengweisong/article/details/45424325

该篇内容就是由软件教程库(原文链接:https://www.itjcku.com/9999/1091341.html)小编为各位整理

阅读全部内容


Tags:拓扑线段

返回首页



推荐内容

【转自mos文章】使用单条sql来查询出awr中的syatemstatistics

使用单条sql来查询出awr中的syatem statistics 参考自: how to monitor system ...

I.MX6Q(TQIMX6Q/TQE9)学习笔记——新版BSP之u-boot移植

前段时间就开始学习i.mx6q了,但是最近工作实在是忙,间断了一些时间了。为了提高移植效率,还是考虑移植freescal ...

eclipse应用技巧

最近发现eclipse作为ide还是有很多值得探索的使用技巧的,转载一下他人整理好的资源以做分享。 快捷键的使用,加速 ...

Mysql创建数据库的排序规则中文选择哪种编码

mysql中文编码 mysql创建数据库的排序规则 中文 选择哪种编码原文地址:http://blog. ...

线性表简述

一、简单实现增,删,改、查 package datatructs; /** * 表接口 */ public int ...

android测试本地服务调试流程

我今天调试的整个过程 1,安卓发现连不上本地的tomcat 2,使用浏览器直接尝试,发现可以连上 3,怀疑是安卓app和 ...

设计模式1

静态工厂模式,工厂方法模式,抽象工厂模式 工厂方法改进了添加新产品时,静态工厂不满足的开-闭原则;而抽象工厂满足了当产品 ...

c语言文件操作总结

#includelt;stdio.hgt; /********************************** ...

(c#)如果添加的字段中已经有了身份证号码,则年龄和性别和出生年月可得

//把界面文本框里面的身份证号进行提取,以二代身份证为例 model.ecardid = txt_cardno. ...

Scrum时间估算

在新公司里,不懂软件工程的产品经理经常逼迫研发人员作出很不靠谱的时间估算。常见场景有下面这些: 需求未细化的情况下要求给 ...

C++11中uniforminitialization和initializer_list

c++11中出现了uniform initialization的概念: int a1 = {1};//ok int a ...

关于Scrum

最近某些产品经理发出下两周的工作计划的时候,喜欢带上sprint这个字眼,看上去貌似是要走敏捷开发这一套,只可惜,我觉得 ...

输入输出简单解释

;汇编指令,表示程序将被汇编成能在intel386系列及以上的计算机上运行.386;model flat 表明程序使用保 ...

2015第18周五问题即机会

问题即机会,当一切问题都不存在的时候,请问你的机会在哪里? 你能达到怎样的境界,取决于你怎样认识这个世界。对于问题,有人 ...

solr配置方案

http://www.sjsjw.com/kf_cloud/article/44_5945_1823.asp cento ...

什么是二维码?

二维码,业界当然是人人听说,人人用过。 这个话题,我倒是百感交集,我一直认为,我有一种二维码情节。 一方面, 我自认 ...

1475:方格取数

1475: 方格取数 time limit:5 secmemory limit:64 mbsubmit:578solv ...

敏捷开发宣言(一)

原文: inpiduals and interactionsover processes and tools worki ...

(C#)一个项目的配置和增删改查

一、windows窗体项目环境配置步骤 1.文件mdash;gt;新建mdash;gt;项目mdash;gt;windo ...

比例简化

题目描述description 在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示 ...

sockaddr和sockaddr_in的区别

struct sockaddr和struct sockaddr_in这两个结构体用来处理网络通信的地址。 在各种系统调用 ...

基于Html5的智能家居手机客户端设计(一)——找到openhab的rest

今天开始我的毕业设计,基于html5的智能家居手机客户端设计。挑剔了好久,终于找到我可以使用国外开源项目智能家居核心 ...

阅读《大道至简--软件工程实践者的思想》有感(3)

阅读完《大道至简--软件工程实践者的思想》,明白了软件与程序的区别,《战国策-秦策》中的那句话,王不如远交而近攻, ...

10条建议让你创建更好的jQuery插件

前言:在开发过很多 jquery 插件以后,我慢慢的摸索出了一套开发jquery插件比较标准的结构和模式。这样我就可以 ...

nexus7升级失败后手动刷系统

http://bbs.gfan.com/android-6934570-1-1.html 步骤如下: 1. 下载a ...

SWUSTOJ爬不出去的水井(0333)

爬不出去的水井(0333) time limit(ms): 1000memory limit(kb): 6 ...

移动端Web开发注意点

不用考虑浏览器兼容性 移动端开发主要对象是手持设备,其中绝大部分是ios和android系统,so,在开发此类页面时不必 ...

CDN云主机与传统虚拟主机功能对比

cdn云主机与传统虚拟主机功能对比   传统的虚拟主机都是单台服务器,一旦机器硬件损坏、ip被封、机房网络故障等,都将导 ...

找斐波那契数列中的第N个数

题目描述 description 用递归的方法求斐波那契数列中的第n个数 输入输出格式input/output 输入格 ...

nginx中ngx_list的数据结构

今天没事了,在查看nginx源代码中看到ngx_list的结构,发现设计为链表数组的形式,不知道为什么这样设计 str ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com