[USACO2004][poj2375]Cow Ski Area（在特殊图上用floodfill代替强联通算法）
浏览数：45 /
时间：2015年06月11日
http://poj.org/problem?id=2375
题意：一个500*500的矩形，每个格子都有一个高度，不能从高度低的格子滑到高度高的格子（但相等高度可以滑），已知可以在2个相邻格子上加桥，使得无视他们的高度就可以互相滑，问最少加多少桥可以使得在任一个格子上都能到达任一个格子。
分析：很容易看出这就是相当于在一个有向图上至少加多少边可以使得其强联通，ans=max(入度0的点数,出度为0的点数），很好理解，可以把出度为0的点挂一条边到入度为0的点上，多了的随便挂。那么现在面临的问题的就是要把25000个点先求强连通分量缩点，但是一般的算法会爆栈（其实手写栈也行……），那么鉴于这图的特殊性——能缩点的点集必定是相连的高度相等的块！~！！！！！那么就简单了，对原图floodfill，分出来的块作为一个缩的点，然后就解决了……
[USACO2004][poj2375]Cow Ski Area（在特殊图上用floodfill代替强联通算法）,,5-wow.com
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
