首页 > 其他分享 >E. Edge Reverse

E. Edge Reverse

时间:2023-02-12 23:23:27浏览次数:58  
标签:ch Reverse int long Edge low dfn now

E. Edge Reverse

思路

二分建图,然后缩点。
如果只有1个点入度为0,那就是满足条件的

代码

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using pdd=pair<double,double>;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define TT int _=read();while(_--)
#define int long long
using ll=long long;
const ll inf=1e18;
//#define double long double
#define endl '\n'
const int M=2e5+5;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

inline void print(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x/10)print(x/10);
    putchar(x%10+'0');
}

int n,m;
int u[M],v[M],w[M];

int h1[M],h2[M],ne[M<<2],e[M<<2],tot;
void add(int h[],int from,int to) {
    e[++tot]=to;  ne[tot]=h[from];  h[from]=tot;
}

int dfn[M],low[M],cnt;
int id[M],scnt;
bool vis[M];
stack<int>st;
void tarjan(int now) {
    dfn[now]=low[now]=++cnt;
    st.push(now);
    vis[now]=1;
    for(int i=h1[now];i;i=ne[i]) {
        int to=e[i];
        if(dfn[to]==0) {
            tarjan(to);
            low[now]=min(low[now],low[to]);
        }
        else if(vis[to])low[now]=min(low[now],dfn[to]);//这里是dfn
    }
    if(dfn[now]==low[now]) {
        scnt++;
        while(1) {
            int k=st.top();
            st.pop();
            vis[k]=0;
            id[k]=scnt;
            if(k==now)break;
        }
    }
}

int in[M];
void init() {
    cnt=scnt=0;
    for(int i=1;i<=n;i++)dfn[i]=vis[i]=low[i]=id[i]=in[i]=0;
    for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);//缩点
    for(int i=1;i<=n;i++)//重构图
        for(int j=h1[i];j;j=ne[j]) {
            int to=e[j];
            if(id[i]!=id[to]) {
                add(h2,id[i],id[to]);
                in[id[to]]++;
            }
        }//图建好了
}

bool check(int x) {
    tot=0;
    for(int i=1;i<=n;i++)h1[i]=h2[i]=0;//清空
    for(int i=1;i<=m;i++) {
        add(h1,u[i],v[i]);
        if(w[i]<=x)add(h1,v[i],u[i]);
    }//第一次建图
    init();
    
    int f=0;
    for(int i=1;i<=scnt;i++)
        if(!in[i])f++;
    return f==1;
    //一共有scnt个点
}
//也就是缩点走图
//两个环的话,也是不行的
//也就是有环的存在,所以有干扰


signed main() {
    TT {
        n=read(),m=read();
        for(int i=1;i<=m;i++) {
            u[i]=read();
            v[i]=read();
            w[i]=read();
        }
        int l=0,r=1e9,ans=-1;
        while(l<=r) {
            int mid=(l+r)/2;
            if(check(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
//二分,然后把那些边能双向找出来就可以了
//然后怎么判断这个点可以到达其他的所有的点呢??
//出度为0的点只有1个,检查一下子就可以了
//难道是判断的条件有问题吗

标签:ch,Reverse,int,long,Edge,low,dfn,now
From: https://www.cnblogs.com/basicecho/p/17114985.html

相关文章

  • Edge浏览器启动后上传数据
    Edge浏览器启动后上传数据最近发现edge在启动后,未打开任何标签的情况下,上传数据具体是什么还不太清楚,你有遇到这种情况吗?猜测:更新版本,备份数据?文章来源:刘俊涛的博客......
  • 图形学数据结构 half-edge
    这个东西,看了之后只有一个感觉WC你看了之后,很可能会感觉 俺也一样这是​​https://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml​​介绍是用来精细化......
  • win10edge浏览器个人账户退出登录后再次登录自动登录问题
     edge浏览器退出登录后,再次点击登录以同步数据会自动登录,可查看书签等个人数据解决方法:先在浏览器里面退出账户。1.设置--电子邮件和账户--管理2.登录后--安全--安......
  • 微软正式发布ChatGPT版必应搜索和Edge
    2月8日消息,微软公司周二发布了新版必应搜索引擎和Edge浏览器,采用了ChatGPT开发商OpenAI的最新技术,旨在通过率先提供更具对话性的网络搜索和创建内容的替代方式,削......
  • Educational Codeforces Round 72 (Rated for Div. 2)D. Coloring Edges 神仙规律
    D.ColoringEdgestimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputYouaregivenadirectedgraphw......
  • chrome、Edge浏览器显示“您的浏览器受管理”是被植入病毒或其它程序了吗?
    这是被植入病毒吗?我经常使用Chrome插件,有些插件调皮设置了这个用来重定向你的网址链接,从而实现广告收入打开chrome://management/查看如否处于托管状态打开chrome://po......
  • (转)[Journey with golang] 1. Basic knowledge
    原文:https://www.cnblogs.com/JHSeng/p/12128461.html这一章介绍golang的一些基础知识。golang写起来跟c++很不一样,在我看来,它更像是c++/java/python的混合体,再经过一系列......
  • [西湖论剑 2023 初赛] Reverse赛题复现
    BabyRE有人昨天以为rc4用的就是空秘钥,那么他是谁呢通过在字符串里找到DASCTF的关键字,一直交叉引用可以找到主要逻辑这里注册的三个函数就是整个题的流程了第一个函数......
  • CF1616G Just Add an Edge
    CF1616GJustAddanEdge一题做了半年,什么水平?看到这道题,先从无解的条件入手?感觉根本没办法弄啊!但是题目中有一个很厉害的性质,就是给定的边满足\(u<v\),所以如果不需......
  • 【工具】-Reverse-DIE(Detect-It-Easy)
    关于DetectItEasy,或缩写为“DIE”是一个用于确定文件类型的程序。DetectItEasy是一个多功能的PE检测工具,基于QT平台编写,主要用于PE是否加壳侦测。“DIE”是......