D题
因为细节错误,最后一分钟才A出来。。。。。。。
首先,我们有一个很明显的贪心。
就是,我们从左到右去枚举边的话,肯定是尽量囊括边 到濒临阈值的情况下
即,我们从最左端一直向右取边,取到极限,算作一组
然后以当前位置为最左端,向右取边取到极限,算作一组
以此类推。
但是我们是无法这样做的,因为我们无法做到动态的查询强连通分量
那么二分可不可以呢?
首先我们以最左端编号1开始二分,找到他可以取到的最右端的编号l2
然后再次二分。。。。
每次二分都使用一次tajan算法验证一遍
但是这样行不行呢?
没试,但是预计会T 我们可以大致感觉到这个复杂度是有点高的
这时,我看了下数据
然后我们可以意识到一个重要的结论:
如果我这个图中只有n个点,那么这个图的重量一定是<=n^2的!!!!
即,我这些点连成了一个强连通
这个结论扩展到边也差不多
如果这个图有m个边,n个点。那么这个图的重量一定是<=m^2 + n-m !!!!!
即,我m条边构造了一个有m个点的强连通分量,然后剩余n-m个孤立的点!!
一句这个结论我们可以做到什么?
这说明了,我们在一开始就可以按照结论,将整个边序列分成大致 个区间!!!!
然后我们需要考虑的就变成了:
从最左边开始,一个一个地合并区间!
能合并就合并,无法合并就取最右(依照我们之前的贪心策略,我们要尽量包含多的边取到上限!)
而这里,如何找到最右边的那个上限,我们就可以使用二分了!
当然,为了不T我们还需要,稍微修改一下tarjan,中遍历点的情况
即:我们只要保留我们所选区间的点即可。
具体实现见代码:
#include<iostream> #include<algorithm> #include<vector> #include<cmath> #include<stack> using namespace std; typedef long long ll; const int max_n = 1e6+100; int n,m; ll k; int es[max_n][2]; vector<int> V; struct edge { int to,next; }E[max_n<<1]; int head[max_n]; int cnt=1; void add(int from,int to) { E[cnt].to=to; E[cnt].next=head[from]; head[from]=cnt++; } int dfn[max_n],low[max_n]; stack<int> st; int colour=0; int color[max_n]; int sz[max_n<<1]; int tot=0; void tarjan(int u) { dfn[u] = low[u] = ++tot; st.push(u); for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (color[v] == 0)low[u] = min(low[u], dfn[v]); } if (low[u] != dfn[u])return; colour++; while (st.top() != u) { color[st.top()] = colour; st.pop(); sz[colour]++; } color[st.top()] = colour; st.pop(); sz[colour]++; } int que[max_n]; int h=0; int cct=0; int vis[max_n]; bool check(int l,int r) { ++cct; int nodes = 0; h=0; for (int i=l;i<=r;++i) { que[++h]=es[i][0]; que[++h]=es[i][1]; if (vis[es[i][0]]!=cct) { vis[es[i][0]]=cct; ++nodes; } if (vis[es[i][1]]!=cct) { vis[es[i][1]]=cct; ++nodes; } } nodes = n-nodes; cnt=1; for (int i=1;i<=h;++i)head[que[i]]=dfn[que[i]]=low[que[i]]=color[que[i]]=0; for (int i=l;i<=r;++i)add(es[i][0],es[i][1]); ll ans = 0; tot=0; colour=0; for (int i=0;i<=h;++i)sz[i]=0; while (!st.empty())st.pop(); for (int i=1;i<=h;++i) { if (dfn[que[i]])continue; tarjan(que[i]); } for (int i=1;i<=colour;++i) ans+= (ll)sz[i]*(ll)sz[i]; return ans+nodes<=k; } int Solve(int cur,int l,int r) { // cout<<cur<<" "<<l<<" "<<r<<endl; --r; if (check(cur,r))return cur; int ans=l-1; int lft = l-1,rgt=r; while (lft<=rgt) { int mid = (lft+rgt)>>1; if (check(cur,mid)) { lft = mid+1; ans = mid; } else rgt =mid-1; } ++ans; if (ans==r+1)return cur; else return ans; } int main() { ios::sync_with_stdio(0); cin>>n>>m>>k; for (int i=1;i<=m;++i)cin>>es[i][0]>>es[i][1]; V.push_back(1); ll lim = sqrt(k); while (lim*lim+n-lim>k)--lim; for (int i=2;i<=m;++i) if (i-V.back()==lim) V.push_back(i); if (V.size()==1) { cout<<1<<endl; return 0; } else if (V.size()==2) { if (check(1,m))cout<<1<<endl; else cout<<2<<endl; return 0; } int ans = 1; V.push_back(m+1); int cur = 1; for (int i=1;i<V.size()-1;++i) { int pre = cur; cur = Solve(cur,V[i],V[i+1]); if (cur!=pre)++ans; } cout<<ans<<endl; }