城市规划

城市规划

题目描述

小a的国家里有n个城市，其中第i和第i - 1个城市之间有无向道路连接，特殊的，第1个城市仅与第2个城市相连

为了减轻道路维护负担，城市规划局局长MXT给出了m个要求，他想让小a断开一些道路，使得任意1 ≤ i ≤ m ，城市xi不能到达城市yi

同时最小化断开道路的数量。

输入描述:

第一行两个整数n, m，分别表示城市的数量和请求的数量 接下来m行，每行两个整数x,y，表示需要使得x不能到达y

输出描述:

输出一个整数，表示最小断开桥的数量

示例1

输入

复制

4 2 1 3 2 4

输出

复制

1

说明

可以断开(2, 3)城市之间的道路

示例2

输入

复制

4 3 1 3 2 4 1 2

输出

复制

2

说明

可以断开(1, 2) (2, 3)之间的道路

思路：

模拟一下样例，想一下，可以把很多边看成区间，如果要想删除的路最少，一定是选择重合区间的最多的部分，也是最短的部分。所以，遍历一遍，一直维护这个状态。

代码：

#include using namespace std;#define ll long long#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)char buf[(1 << 22)], *p1 = buf, *p2 = buf;inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f;}const int maxn=1e5+100;const int INF=0x3f3f3f3f;int *G=new int[(int)1e7 + 10];int main(){ int n,m; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); memset(G,0,sizeof(G)); n=read();m=read(); int u,v; for(int i=1;i<=m;i++) { u=read(); v=read(); if(u>v)swap(u,v); if(!G[u]) { G[u]=v; } else if(G[u]>v) { G[u]=v; } } ll sum=0; int flag=INF; for(int i=1;i<=n;i++) { if(flag==i) { sum++; flag=INF; } if(G[i]&&G[i]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。