java 车站分级_【图论经典题】NOIP2013 普及组 T4 车站分级（两种方法）

╰半夏微凉° 2022-11-05 03:26 11阅读 0赞

Solution

主要是按车站分级(就是按照题目意思来)和按车分级两种方法。

方法一：按车站分级，我们知道一辆车经过的车站的等级一定大于没经过的车站的等级，这样就可以根据大小关系建议一张拓扑图，然后拓扑排序。

时间复杂度：O(MN^2) 但是常数很小可以过

方法二：

https://blog.csdn.net/ta201314/article/details/46659541

我们可以这样理解题意：每辆车有一个等级x，这辆车经过所有等级大于等于它的车站，我没有一个想法：车的等级数等于车站的等级数，为什么？首先车站的最大等级大于等于车的等级，其次……(还是看这个网站的吧。)

CODE

按车站

\#includeusing namespace std;

const int MAXN=1010;

bool e\[MAXN\]\[MAXN\],flag\[MAXN\];

int d\[MAXN\],q\[MAXN\],b\[MAXN\],n,m,head,tail,num,ans;

int main()

\{

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++)

\{

scanf("%d",&num);

memset(flag,false,sizeof(flag));

for (int j=1;j<=num;j++)

scanf("%d",&b\[j\]),flag\[b\[j\]\]=true;

for (int j=b\[1\];j<=b\[num\];j++)

if (!flag\[j\])\{

for (int k=1;k<=num;k++)

if (!e\[b\[k\]\]\[j\]) e\[b\[k\]\]\[j\]=true,d\[j\]++;

\}

\}

head=tail=0;

for (int i=1;i<=n;i++)

if (!d\[i\]) q\[tail++\]=i;

while (head按车分级\#includeusing namespace std;

const int MAXN=1010;

bool flag\[MAXN\];

int b\[MAXN\],d\[MAXN\],q\[MAXN\],Head\[MAXN\];

int tot,n,m,head,tail,ans;

struct node\{

int s,t;

int sum\[MAXN\];

\}train\[MAXN\];

struct Edge\{

int next,v;

\}edge\[MAXN\*MAXN\];

void add\_edge(int x,int y)

\{

tot++; d\[y\]++;

edge\[tot\]=(Edge)\{Head\[x\],y\};

Head\[x\]=tot;

\}

int main()

\{

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++)

\{

int num;

scanf("%d",&num);

memset(flag,false,sizeof(flag));

for (int j=1;j<=num;j++)

scanf("%d",&b\[j\]),flag\[b\[j\]\]=true;

train\[i\].s=b\[1\]; train\[i\].t=b\[num\];

for (int j=b\[1\];j<=b\[num\];j++)

train\[i\].sum\[j\]=train\[i\].sum\[j-1\]+(flag\[j\]?1:0);

\}

m++;

train\[m\].s=1; train\[m\].t=n;

for (int i=1;i<=n;i++) train\[m\].sum\[i\]=i;

for (int i=1;i<=m;i++)

for (int j=1;j<=m;j++)

\{

if (i==j) continue;

int x,y,si,sj;

x=max(train\[i\].s,train\[j\].s);

y=min(train\[i\].t,train\[j\].t);

if (x>y) continue;

si=train\[i\].sum\[y\]-train\[i\].sum\[x-1\];

sj=train\[j\].sum\[y\]-train\[j\].sum\[x-1\];

if (sisj) add\_edge(j,i);

\}

head=tail=0;

for (int i=1;i<=m;i++)

if (!d\[i\]) q\[tail++\]=i;

while (head

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 P1983-车站分级

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

Myth丶恋晨/ 2023年06月01日 08:55/ 0 赞/ 2 阅读

相关 P1981 [NOIP2013 普及组] 表达式求值

[P1981 \[NOIP2013 普及组\] 表达式求值][P1981 _NOIP2013 _] 题目描述给定一个只包含加法和乘法的算术表达式，请你编程计算表达式

落日映苍穹つ/ 2023年01月13日 09:34/ 0 赞/ 301 阅读

相关 2013年NOIP普及组：无向图-连通图问题

题目：在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图,至少要删去其中的( )条边 ![在这里插

素颜马尾好姑娘i/ 2022年12月04日 07:42/ 0 赞/ 131 阅读

相关 java 车站分级_【图论经典题】NOIP2013 普及组 T4 车站分级（两种方法）

Solution 主要是按车站分级(就是按照题目意思来)和按车分级两种方法。方法一：按车站分级，我们知道一辆车经过的车站的等级一定大于没经过的车站的等级，这样就可以根据大

╰半夏微凉°/ 2022年11月05日 03:26/ 0 赞/ 12 阅读

相关【基础练习】【拓扑排序】codevs3294 车站分级题解

题目来源：NOIP2013 普及第四题题目描述 Description 一条单向的铁路线上，依次有编号为1, 2, …, n的n个火车站。每个火车站都

蔚落/ 2022年08月05日 02:44/ 0 赞/ 164 阅读

相关 NOIP 1998 车站(规律)

题目描述火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人

水深无声/ 2022年05月17日 09:57/ 0 赞/ 162 阅读

相关 NOIP 2013初赛普及组C/C++答案详解

试题和答案： https://wenku.baidu.com/view/aa2bc10b5022aaea988f0f77.html?re=view 一、单选题 1

深碍√TFBOYSˉ_/ 2022年05月09日 07:03/ 0 赞/ 262 阅读

相关 NOIP普及组初赛题型分析

初赛的考察内容的一部分是计算机的基础知识，比如进制转换，工作原理，算法原理、历史事件名人等。这些对于大部分第一次参加noip的同学来说应该比较陌生，这样的知识只能通过平时的积累

曾经终败给现在/ 2022年05月06日 05:28/ 0 赞/ 273 阅读

相关洛谷 1062 NOIP2006普及T4 数列

![1215829-20180411082152092-1296113100.png][] 【题解】　　鲜活的水题。。我们把数列换成k进制的，发现数列是001,010,0

秒速五厘米/ 2021年12月10日 03:57/ 0 赞/ 231 阅读

相关 java日志分级概要

记录一下，用于以后的规范化 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

爱被打了一巴掌/ 2021年07月20日 20:44/ 0 赞/ 374 阅读