专栏首页Zaqdt_ACMCodeforces Round #532 (Div. 2) E. Andrew and Taxi(二分+拓扑排序)

Codeforces Round #532 (Div. 2) E. Andrew and Taxi(二分+拓扑排序)

题目链接:https://codeforces.com/contest/1100/problem/E

       题意是n个点,m条有向边,每条边都有一个权值,将某些边变向,使得图变成一个无环图,要使所有变向的边中权值最大的最小,输出这个最大的最小值和变向的边。

       大致思路是二分答案,然后用拓扑排序去判断是否存在环。具体的操作是我们把每次枚举的mid作为建边的依据,把大于mid的边建起来,因为答案是变向的边的最大值,所以比mid大的边都是不用变向的边,所以将他们建好边以后判断一下图是否是无环图(入队个数等于n就是无环图),如果不是无环图的话,说明这些边有些还需要变向,那么就扩大mid的值。如果这个图是一个无环图的话,就更新ans数组,更新的过程是它的权值要小于等于mid,然后按它的拓扑顺序进行变向,并将mid缩小去找更小的答案。有一个讲的不错的文章,对于更新ans数组的过程有详细的解释,可以去看看:https://www.geeksforgeeks.org/


AC代码:

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct Node{
  int x, y, w;
}Edge[maxn];
int pre[maxn], dep[maxn], pos[maxn];
vector<int> ans;
int n,m;

bool Check(int xx){
  vector<int> v[maxn];
  memset(dep, 0, sizeof(dep));
  for(int i=1;i<=m;i++){
    if(Edge[i].w > xx){
      v[Edge[i].x].push_back(Edge[i].y);
      dep[Edge[i].y] ++;
    }
  }
  queue<int> q;
  int cnt = 0, yy = 0;
  for(int i=1;i<=n;i++) if(dep[i] == 0) q.push(i), pos[i] = ++cnt, yy++;
  while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int i=0;i<v[u].size();i++){
      int to = v[u][i];
      if(--dep[to] == 0){
        q.push(to);
        pos[to] = ++ cnt;
        yy ++;
      }
    }
  }
  if(yy != n) return false;
  ans.clear();
  for(int i=1;i<=m;i++){
    if(Edge[i].w <= xx && pos[Edge[i].y] < pos[Edge[i].x]) ans.push_back(i);
  }
  return true;
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&Edge[i].x,&Edge[i].y,&Edge[i].w);
  }
  int l = 0, r = 1e9+2, mid, xx;
  while(l <= r){
    mid = (l + r) >> 1;
    if(Check(mid)) r = mid - 1, xx = mid;
    else l = mid + 1;
  }
  // Check(xx);     我觉得这里不需要再更新一次ans数组了 因为xx和ans是同步更新的
  printf("%d %d\n",xx, ans.size());
  for(int i=0;i<ans.size();i++){
    printf("%d ", ans[i]);
  }
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NYOJ 123 士兵杀敌(四) (线段树+树状数组)

    题目连接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=123

    Ch_Zaqdt
  • HDU 6447 YJJ's Salesman(离散化+树状数组+dp)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6447

    Ch_Zaqdt
  • Codeforces Round #513 A. Phone Numbers(水题)

    题目链接:http://codeforces.com/contest/1060/problem/A

    Ch_Zaqdt
  • 剑指Offer LeetCode 面试题53 - II. 0~n-1中缺失的数字

    一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个...

    TrueDei
  • 剑指offer——数字在排序数组中出现的次数

    由于是有序数组,那么查找采取二分法。找到k在数组中的位置,在向前和向后遍历是否有重复的。

    AI那点小事
  • 防范攻击 加强管控 - 数据库安全的16条军规

    近日的数据安全事故,引发了很多企业的普遍关注,而不少用户从彻查中确实发现自己的数据库已经被注入,这为大家上了数据安全的重要一课。 甚至有的企业要求停用PL/SQ...

    数据和云
  • 洛谷P4093 [HEOI2016/TJOI2016]序列

    题目描述 佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现...

    attack
  • 交通运输网络安全风险不容忽视,看大数据如何解决大问题

    7月7日,交通运输行业大数据系统与安全实验室(BiDaS-T)启动仪式暨交通运输网络安全战略与技术高峰论坛在同济大学嘉定校区举行。本次论坛聚焦交通运输网络安全风...

    安恒信息
  • Python3与fastdfs分布式文件系统如何实现交互

    注意:client.conf是从fdfs服务器上复制到django代码机器上的文件,需要将里面的base_path路径修改成存放client.conf的路径

    砸漏
  • UOJ#52. 【UR #4】元旦激光炮(交互)

    一种很显然的$log^2n$的做法:首先在$a$中二分,然后再$b,c$中二分。这样可以得到$60$分的好成绩。

    attack

扫码关注云+社区

领取腾讯云代金券