題目鏈接：1037E - Trips

題目大意：有n個人，m天，每天晚上都會有一次聚會，一個人會參加一場聚會當且僅當聚會里有至少k個人是他的朋友。每天早上都會有一對人成為好朋友，問每天晚上最多能有多少人參加聚會。朋友關系不滿足傳遞性。

　　　相當于有n個點，進行m次加邊操作，每次操作后附加一個詢問，問最大點集的大小，使得點集中每個點的度數(shù)均大于等于k

?

題解：如果直接邊加邊詢問可能比較麻煩，本著“正難則反”的原則，我們可以將題目轉化為，初始有m條邊，每次操作是先詢問當前的答案，再刪去一條邊。

　　　現(xiàn)在我們就可以先考慮，如果給你m條邊，問對應的答案是多少，如何求解。這里給出一個定義，稱一個人（點）為無用的，當且僅當沒有人會因為他參加了聚會而參加聚會，否則稱這個人是有用的。對于朋友關系（邊）同理，當且僅當沒有人會因此朋友關系而加入聚會，這條邊才被稱為無用。

　　　顯然，一個度數(shù)小于k的點肯定是無用的，因為他的朋友不到k個，肯定不會去聚會，更不會有人因為他去聚會。接下來我們可以發(fā)現(xiàn)，這個點連出去的邊也肯定是無用的，理由同上。那既然這些邊是無用的了，我們就可以將這些邊刪去，對應的一些點的度數(shù)就會減少，就可能會產(chǎn)生新的“無用點”，這時候我們就要再將這些點以及有連接到這些點的邊刪去，直至剩下的所有點和邊都是有用的。此時，將剩下的這些點全部拿去參加聚會肯定是滿足條件的，因此答案就是剩下的點的個數(shù)。

　　　接下來考慮刪邊的情況，每次刪邊前先檢索這條邊是否還存在（即是否還是有用的），如果他已經(jīng)被當做無用邊刪除了，則這次操作不會對答案產(chǎn)生影響，繼續(xù)進行下一次操作。如果這條邊還是有用的，則刪去這條邊，如果刪去這條邊導致了新的無用點的產(chǎn)生（即出現(xiàn)了度數(shù)小于k的點），則刪除此點和相關的邊，操作方法和預處理時一致。這樣做m次之后再輸出答案就好了。

?

代碼中s表示有用點的集合，d[i]記錄與i相連的有用邊的終點的集合

#include<bits/stdc++.h>
using namespace std;
#define N 200001
int n,m,k,x[N],y[N],ans[N];
set<int>d[N],s;
queue<int>q;
int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]),d[x[i]].insert(y[i]),d[y[i]].insert(x[i]);for(int i=1;i<=n;i++)if(d[i].size()<k)q.push(i);while(!q.empty()){int cur=q.front();q.pop();for(auto nxt:d[cur]){d[nxt].erase(cur);if(d[nxt].size()<k)q.push(nxt);}d[cur].clear();}for(int i=1;i<=n;i++)if(d[i].size()>=k)s.insert(i);for(int i=m;i>=1;i--){ans[i]=s.size();if(d[x[i]].count(y[i])){d[x[i]].erase(y[i]);d[y[i]].erase(x[i]);if(d[x[i]].size()<k)q.push(x[i]);if(d[y[i]].size()<k)q.push(y[i]);}while(!q.empty()){int cur=q.front();q.pop();for(auto nxt:d[cur]){d[nxt].erase(cur);if(d[nxt].size()<k)q.push(nxt);}d[cur].clear(),s.erase(cur);}}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

View Code

?

轉載于:https://www.cnblogs.com/DeaphetS/p/9584564.html

總結

以上是生活随笔為你收集整理的[Manthan, Codefest 18][Codeforces 1037E. Trips]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。