首页 > 其他分享 >CF645D - Robot Rapping Results Report 题解

CF645D - Robot Rapping Results Report 题解

时间:2024-08-27 16:39:33浏览次数:9  
标签:Rapping idx int 题解 void 机器人 CF645D mid 100005

\[Problem \]

有 \(N\) 个机器人,给出 \(M\) 组关系,表示两个机器人的能力关系,问至少需要前几组关系可以确定所有机器人的排名。

\[Solution \]

由于是求最少的前几组关系,而关系越少越难确定排名,关系越多越容易确定,不难发现本题满足单调性,考虑二分。

那么给出关系要求总排名的题,就应该使用拓扑排序实现。

\[Topological\ Sorting \]

对于一个有向图,每次从一个入度为 \(0\) 的节点开始,删除它和它的所有出边,并将它存储到拓扑序列里。

如果图存在环,或者关系不足,那么拓扑排序将无法遍历所有节点(但是本题不考虑环,因为机器人的能力不可能成为一个环)。

剩下的拓扑序列就是机器人的总排名。

\[Code \]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;

int x[100005],y[100005],d[100005];
queue<int>q;

namespace Graph //链式前向星存图
{
    int h[100005],to[100005],nxt[100005],idx;
    void init_graph(void)
    {
        while(!q.empty())
            q.pop();
        memset(d,0,sizeof(d));
        memset(h,-1,sizeof(h));
        idx=0;
    }

    void add_edge(int u,int v)
    {
        to[idx]=v;
        nxt[idx]=h[u];
        h[u]=idx++;
    }
}

using namespace Graph;

bool check(int k)
{
    init_graph();
    for(int i=1;i<=k;i++)
    {
        add_edge(x[i],y[i]);
        d[y[i]]++;//存每个点的入度
    }
    for(int i=1;i<=n;i++)
        if(d[i]==0)q.push(i);
    if(q.size()>1||q.size()==0)return false;
    while(!q.empty())//用 BFS 遍历
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=nxt[i])
        {
            int j=to[i];
            d[j]--;//删边
            if(!d[j])//入度为 0
                q.push(j);
        }
        if(q.size()>1)return false;
    }
    return true;
}

signed main(void)
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>x[i]>>y[i];
    int l=1,r=m,mid;
    while(l<r)//二分
    {
        mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(check(l))
        cout<<l;
    else
        cout<<-1;
    return 0;
}

标签:Rapping,idx,int,题解,void,机器人,CF645D,mid,100005
From: https://www.cnblogs.com/dijkstraphoenix/p/18382982

相关文章

  • AT_code_festival_2017_qualc_d - Yet Another Palindrome Partitioning 题解
    YetAnotherPalindromePartitioning题解题目大意给出一个字符串,求把这个字符串划分成最少的小段,使每个小段都可以经过字母重组后为回文串。题目分析如果暴力的话,需要DFS段数、每一段的左节点、右节点,以及判断是否为回文串,时间复杂度在\(O(|S|^{|S|})\)左右。但是本......
  • Dirsearch-master安装使用及常见问题解决(互联网和内网)
    1、文档概述        本手册适用于帮助初学者快速掌握Dirsearch-master的安装、配置与使用方法。通过阅读本文档,您将能够了解如何搭建Dirsearch-master环境、扫描目标服务器上潜在的敏感文件和目录,并解读生成的报告。此外,本文档还涵盖了常见问题及解决方法,以便您在实际......
  • 【题解】P3210 [HNOI2010] 取石头游戏
    \(\large\mathfrak{1st.\Preamble|}\)前言题目传送门:P3210[HNOI2010]取石头游戏)主要是参考楼下大佬的题解,对于其中没讲到或比较难懂的地方进行讲解,以及配上了图。\(\large\mathfrak{2nd.\Solution|}\)题解楼下大佬的比喻十分形象生动地描绘了俩人去石头的过程:取石子......
  • 题解:P10922 Happybob's Numbers (UBC001B)
    主要思路:贪心,构造。思路构造题,首先明确要删的就是小于\(n\)的数,因为若删了大于等于\(n\)的数就无法进行之后的操作了。那这道题就简单了,先从大到小排序,遇到小于当前长度\(k\)的数,就将这个数删掉,这时长度需减\(1\),毕竟顺序可以自己调,将下一个小于当前\(k\)的数,放到下一......
  • 题解:P5934 [清华集训2012] 最小生成树
    主要思路:网络流。思路先考虑最小生成树,如果一条边边权大于等于选中的边,那么这条边是否删去没有任何影响。按边权排序,对于边\((u,v,L)\),若要加上当且仅当\(u\)和\(v\)并不联通。把所有边权比选定的边的边权小的边拿出来连上,流量均为\(1\),最小割。最大树同理,连上边权比选......
  • 题解:P11007 『STA - R7』Odtlcsu
    评价:简单构造。思路注意题目中的“如果有多解输出任意一种即可”。由于\(a\)与\(a^{2}\)的奇偶性必定是一致的,所以我们可以将情况分为两种。当\(x\)与\(y\)奇偶性不一致时,但由于\(a\)与\(a^{2}\)的奇偶性必定是一致的,所以始终无法构造出正确的序列。但注意题目......
  • P4126 [AHOI2009] 最小割 题解
    DescriptionA,B两个国家正在交战,其中A国的物资运输网中有\(N\)个中转站,\(M\)条单向道路。设其中第\(i\(1\leqi\leqM)\)条道路连接了\(u_i,v_i\)两个中转站,那么中转站\(u_i\)可以通过该道路到达\(v_i\)中转站,如果切断这条道路,需要代价\(c_i\)。现在B国想找出一个......
  • 最大矩阵区间 题解
    题意简述给定\(n\)行\(m\)列矩阵\(A\)。对于每一行\(i\),选择非空区间\([l_i,r_i]\),满足\(\foralli\in[1,n)\),\([l_i,r_i]\)和\([l_{i+1},r_{i+1}]\)相交,即\(\max\{l_i,l_{i+1}\}\leq\min\{r_i,r_{i+1}\}\)。求所有选出区间的\(A_{i,j}\)值......
  • Luogu P4588 数学运算 题解 [ 绿 ] [ 线段树 ]
    LuoguP4588数学运算。虽然是一个很典的题,但里面的思想还是比较值得记录的。假做法一开始看到此题还以为是乘法逆元的模板题,但看到\(m\)与\(M\)不互质,就知道这种做法是假的了。注意exgcd虽然能求模数为合数的逆元,但是要是两数不互质就什么算法都搞不了了。因此,本题不能......
  • Luogu P7250 BalticOI 山峰 题解 [ 蓝 ] [ 模拟 ] [ 并查集 ] [ BFS ]
    LuoguP7250BalticOI山峰。一道大模拟,很暴力,也很难写。建议紫或蓝,标签为模拟、广度优先搜索、并查集。思路首先观察到答案取决于路线上的最低点,所以我们可以把所有点的高度丢进一个桶里,从大到小枚举,尝试更新答案。这应该是个挺经典的trick了。感性理解可以看作所有山都先......