2019河北省CCPC 舔狗【贪心】

传送门

思路：每个舔狗只会喜欢一个人，每个人的选择就只有一个，要满足配对的舔狗数量最多，我们就应该选择喜欢人数少的舔狗来优先进行匹配。一个舔狗被多少人喜欢，就是这个点的入度。如果喜欢他的其中一个舔狗被配对了，那么这个舔狗的入度就应该减去1。我们就利用优先队列来维护每个舔狗的入度，然后去判断是否可以帮这只舔狗配对。

 

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<new>
#include<vector>

#define MT(a, b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5;

int n,like[maxn],in[maxn];
int vis[maxn],ans;

struct node{
    int e,d;
    bool friend operator<(node a,node b){
        return a.d>b.d;     ///优先选择入度少的舔狗
    }
};
void solve(){
    priority_queue<node>q;
    for(int i=1;i<=n;i++){
        q.push(node{i,in[i]});
    }
    while(!q.empty()){
        node w=q.top();
        q.pop();
        ///如果已经被选择,或者他喜欢的人也配对了
        if(vis[w.e]||vis[like[w.e]])
            continue;   
        ans+=2;
        vis[w.e]=vis[like[w.e]]=1;///这两只舔狗配对
        ///舔狗喜欢的人的入度减去1
        q.push(node{like[like[w.e]],--in[like[like[w.e]]]});
    }
    printf("%d\n",n-ans);   ///输入未配对的舔狗数
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&like[i]);
        in[like[i]]++;
    }
    solve();
    return 0;
}