BZOJ4484: [Jsoi2015]最小表示(拓扑排序乱搞+bit…
2018-06-17 20:53:30来源:未知 阅读 ()
Submit: 348 Solved: 172
[Submit][Status][Discuss]
Description
【故事背景】
还记得去年JYY所研究的强连通分量的问题吗?去年的题目里,JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的JYY,今年又琢磨起了“删边”的问题。
【问题描述】
对于一个N个点(每个点从1到N编号),M条边的有向图,JYY发现,如果从图中删去一些边,那么原图的连通性会发生改变;而也有一些边,删去之后图的连通性并不会发生改变。
JYY想知道,如果想要使得原图任意两点的连通性保持不变,我们最多能删掉多少条边呢?
为了简化一下大家的工作量,这次JYY保证他给定的有向图一定是一个有向无环图(JYY:大家经过去年的问题,都知道对于给任意有向图的问题,最后都能转化为有向无环图上的问题,所以今年JYY就干脆简化一下大家的工作?)。
Input
输入一行包含两个正整数N和M。
接下来M行,每行包含两个1到N之间的正整数x_i和y_i,表示图中存在一条从x_i到y_i的有向边。
输入数据保证,任意两点间只会有至多一条边存在。
N<=30,000,M<=100,000
Output
输出一行包含一个整数,表示JYY最多可以删掉的边数。
Sample Input
1 2
2 3
3 5
4 5
1 5
1 3
Sample Output
HINT
Source
By 佚名上传
#include<cstdio> #include<iostream> #include<bitset> #include<cstring> #include<queue> #include<algorithm> #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++) char buf[1<<23],*p1=buf,*p2=buf; using namespace std; const int MAXN=30001; 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; } struct node { int u,v,nxt; }edge[MAXN*10]; int head[MAXN],num=1; inline void AddEdge(int x,int y) { edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++; } int VisitTime[MAXN];//i是第几个入队的 int InputTime[MAXN];//第i个入队的是谁 int inder[MAXN]; bitset<MAXN>can[MAXN];//联通性 int N,M; int to[MAXN]; int comp(const int &a,const int &b) { return VisitTime[a]<VisitTime[b]; } void Topsort() { queue<int>q; for(int i=1;i<=N;i++) if(inder[i]==0) q.push(i); int tot=0; while(q.size()!=0) { int p=q.front();q.pop(); InputTime[++tot]=p; VisitTime[p]=tot; for(int i=head[p];i!=-1;i=edge[i].nxt) { inder[edge[i].v]--; if(inder[edge[i].v]==0) q.push(edge[i].v); } } int ans=0; for(int i=N;i>=1;i--) { int x=InputTime[i],tot=0; can[x][x]=1; for(int j=head[x];j!=-1;j=edge[j].nxt) to[++tot]=edge[j].v; sort(to+1,to+tot+1,comp); for(int j=1;j<=tot;j++) { if(can[x][to[j]]) ans++; else can[x]|=can[to[j]]; } } printf("%d",ans); } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif memset(head,-1,sizeof(head)); N=read(),M=read(); for(int i=1;i<=M;i++) { int x=read(),y=read(); AddEdge(x,y); inder[y]++; } Topsort(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【题解】P1440 求m区间内的最小值 2019-12-23
- 最小割最大流定理&残量网络的性质 2019-12-17
- 图论-最小生成树<Kruskal> 2019-10-28
- 【学习笔记】RMQ-Range Minimum/Maximum Query (区间最小/ 2019-08-26
- 洛谷 P2085 最小函数值 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash