Main » 2013 October 18 » [NOIP2012模拟赛No.10]连通分支
4:17 PM [NOIP2012模拟赛No.10]连通分支 |
二分答案+BCJ#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 300010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int x[N],y[N],f[N],n,m,X,flag[N]; int getf(int x){if (f[x]!=x) f[x]=getf(f[x]);return f[x];} bool check(int k) { int i; FOR(i,1,n) f[i]=i; memset(flag,0,sizeof(flag)); FOR(i,1,m) { if (x[i]<=k||y[i]<=k) continue; int fa=getf(x[i]),fb=getf(y[i]); if (fa!=fb) f[fa]=fb; } FOR(i,1,n) { int F=getf(i); flag[F]++; if (flag[F]>X) return 0; } return 1; } int main() { scanf("%d%d%d",&n,&m,&X);int i; FOR(i,1,m) scanf("%d%d",&x[i],&y[i]); int l=0,r=n,ans; while (1) { if (r-l==1) {if (check(l)) ans=l;else ans=r;break;} int M=(l+r)>>1; if (check(M)) r=M;else l=M; } printf("%d\n",ans); } |
|
|
| Total comments: 0 | |