2019河北省大学生程序设计竞赛（重现赛）J-舔狗 （拓扑排序）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2019河北省大学生程序设计竞赛（重现赛）J-舔狗 （拓扑排序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1668字，纯文字阅读大概需要3分钟。

内容图文

题目链接：https://ac.nowcoder.com/acm/contest/903/J

---

题意：给你 n 个舔狗和他喜欢的人，让你俩俩配对（只能和喜欢它的和它喜欢的），求剩下的单身狗数量。

思路：类似于拓扑排序，由入度最少的边开始配对，也就是被最少的舔狗喜欢的（甚至是没有）。将已经配对的舔狗进行标记，更新入度后重新加入优先队列，最后用总数减去标记数就是答案了。

总结：一开始我的思路是对的呐，但是我和我的小伙伴卡在没办法处理同时配对2个点和维护他们入度，看完别人的处理才发现自己是局限于找入度为0而不是找入度最少。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<cstring>
 5 #include<vector>
 6 using namespace std;
 7 const int maxn = 1e6 + 5;
 8 const int INF = 0x3f3f3f3f;
 9 int n;
10 int in[maxn];
11 int vis[maxn];
12 int like[maxn];
13 struct node{
14     int u,v;//u是编号，v是入度。
15     bool friend operator<(node a,node b)//优先队列使入度小的排在前面
16     {
17         return a.v > b.v;
18     }
19 };
20 void solve()
21 {
22     int ans = 0;
23     priority_queue<node> q;
24     for(int i = 1;i<= n;i++)
25     {
26         q.push( node{i,in[i]} );//将所有点加入队列;
27     }
28     while(!q.empty())
29     {
30         node w = q.top(); q.pop();
31         if(vis[w.u] || vis[ like[w.u] ]) continue; //如果他或者他喜欢的配对了就不能配了;
32         ans += 2;
33         vis[w.u] = 1;
34         vis[ like[w.u] ] = 1;
35         //更新入度，反正优先队列，多跑几次没关系
36         q.push( node{like[like[w.u]],--in[ like[like[w.u]] ] } );//like[like[w.u]] 是指舔狗喜欢的人喜欢的人。
37     }
38     printf("%d\n",n-ans);
39 }
40 int main()
41 {
42     scanf("%d",&n);
43     for(int i = 1;i <= n;i++)
44     {
45         scanf("%d",&like[i]);
46         in[like[i] ]++;
47     }
48     solve();
49     return 0;
50 }

 

内容总结

以上是互联网集市为您收集整理的2019河北省大学生程序设计竞赛（重现赛）J-舔狗 （拓扑排序）全部内容，希望文章能够帮你解决2019河北省大学生程序设计竞赛（重现赛）J-舔狗 （拓扑排序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---