/* 一个凸多边形n<=10000,cut了m次,每一刀不相交 求边数最多那块的边数
这题用错误的做法搞了很久,浪费大量时间,囧![](http://www.cppblog.com/Images/dot.gif) 然后洗澡时想到了可以通过每次找一个“最小的环”来做 类似: http://watashi.ws/blog/970/andrew-stankevich-3-solution/ zoj 2361 上面这题十分推荐!!! 上面那题是按照极角排序,不过这题可以按照点的编号排序即可
多边形的顶点看成图的顶点,多边形的边是边,cut也看成边(双向的边) 建好图后,对每个点找它所在的环(可能多个) 比如现在已经有边pre->now,那么就在now的邻接边中找第一个比pre小的点 (没有的话,就最大那个) 这样,走出的环就是最小的了(也即环内没有边) 画个图就清楚了 8 4 2 8 2 4 4 6 6 8 */ #include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cstring> #include<cmath> #include<string> #include<cstdlib> #include<vector> #include<cstdio> #include<set> #include<list> #include<numeric> #include<cassert> #include<sstream> #include<ctime> #include<bitset> #include<functional>
using namespace std;
const int INF = 0x3f3f3f3f; const int MAXN = 10086;
vector<int> e[MAXN];
int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif
for (int N, M; ~scanf("%d%d", &N, &M); ) { for (int i = 1; i <= N; i++) { e[i].clear(); e[i].push_back(i == N ? 1 : i+1); //e[i].push_back(i == 1 ? N : i-1);这条边不用加 } int x, y; for (int i = 0; i < M; i++) { scanf("%d%d", &x, &y); if (x > y) swap(x, y); //双向的边 e[x].push_back(y); e[y].push_back(x); } for (int i = 1; i <= N; i++) { sort(e[i].begin(), e[i].end()); } int ans = 0; for( int i = 1; i <= N; i++) { //cout<<endl<<i<<": \n"; for (vector<int>::iterator it = e[i].begin(), jt; it != e[i].end(); ) { int pre = i, now = *it, len = 1; //每次在now中寻找第一个小于pre的,这样就是最小的环了,类似极角最小 while (now != i) { //cout<<pre<<" "<<now<<endl; len ++; jt = lower_bound(e[now].begin(), e[now].end(), pre); //不能写成--jt < e[now].begin(),因为--jt不再属于e[now]的范围了 if (jt == e[now].begin()) { jt = --e[now].end(); } else jt --; pre = now; now = *jt; e[pre].erase(jt); } it = e[i].erase(it); //cout<<len<<endl; ans = max(ans, len); } } printf("%d\n", ans); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
![](/images/xml.gif)
|
|