题目链接

题目大意

贵族i有一个自己的权力a[i],默认a[i]=i

定义:一个贵族是脆弱的,当且仅当他有朋友&&他的所有朋友的权利都比他大。

n个点,m条边(朋友关系)。给定q次操作,每次操作有如下几种方式:

  1. 添加uv的朋友关系
  2. 删除uv的朋友关系
  3. 进行一次查询

查询过程:把所有脆弱的贵族“杀死”,同时意味着断掉他的“朋友关系”,然后可能会有贵族因为别的贵族死亡而变得脆弱,然后再“杀死”这些脆弱的贵族……重复上述过程,直至没有脆弱的贵族,输出此时贵族的人数。

注意,在查询过后,“杀死”的贵族会“复活”,朋友关系也会继续存在。

解题思路

由于上述的过程十分类似于拓扑排序,因此我赛场上首先想到拓扑排序,但是由于自己水平过菜(想得太多&&代码实现能力过差)前后写了200多行也没搞出来。

其实可以用到拓扑序的思想,记录每个点的入度和出度。当一个贵族的朋友比他权力低,视作从低权力向高权力连一条有向边。低权力贵族的出度++,高权力贵族的入度++。删边同理

而实际上什么时候这个贵族不是脆弱的只取决于出度(和入度无关)。当一个贵族的出度=0,意味着他没有权力比他大的朋友,因此他永远不会死。所以本题仅需考虑每个点的出度即可。

千万不要考虑入度……因为无论入度是否等于0,只要出度大于0都会被最后消灭掉。

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+7;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
int T,t;
int n,m,k;
int r[N],c[N];//入度 出度
int opt;
int ans;

signed main(){
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    T=1;
    while(T--){
        cin>>n>>m;
        int u,v;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            if(u>v) swap(u,v);
            r[v]++;
            c[u]++;
        }
        for(int i=1;i<=n;i++){
            if(c[i]==0) ans++;
        }
        cin>>t;
        while(t--){
            cin>>opt;
            if(opt==1){
                cin>>u>>v;
                if(u>v) swap(u,v);
                r[v]++;
                c[u]++;
                if(c[u]==1) ans--;
            }
            if(opt==2){
                cin>>u>>v;
                if(u>v) swap(u,v);
                r[v]--;
                c[u]--;
                if(c[u]==0) ans++;
            }
            if(opt==3){
                cout<<ans<<"\n";
            }
        }
    }
    return 0;
}
分类: 补题

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注