题解：Edge Reverse

题目：

https://codeforces.com/problemset/problem/1777/E

我的最初想法是：先进行缩点，然后加入剩余的边，忽略边的方向（因为剩余的边都可以调整方向），用并查集维护连通性，只要有一个点没有加入并查集，说明有不止一个连通块，那么就直接输出-1。然后特判完后，可以考虑二分答案，然后就卡住了，不知道怎么check。

此题的关键点在于：缩点后的图是一个有向无环图(DAG)，在DAG上存在一个节点能到达其他所有节点的充要条件是只有一个入度为0的点（且能到达其他所有节点的点即是该入度为0的点）

证明：
充分性：在DAG上存在一个节点能到达其他所有节点，那么只有一个入度为0的点。
反证法，假设该点为u入度不为0，那么肯定存在一个节点设为v连接了u，而u可以到达所有节点，u能到达v，v又能到达u，存在环在DAG上是不合法的，所以u的入度为0。假设入度为0的点不止一个，设另一个入度为0的节点为v，由于没有边指向v，所以没有节点可以到达v，与u可以到达其他所有节点矛盾。所以有且仅有一个入度为0的点。

必要性：DAG上只有一个入度为0的点，那么该点可以到达其他所有节点。
设入度为0的点为u，随机选取一个点为v，如果v等于u，自己到自己，结论直接成立。v不等于u，因为v的入度不为0，那么一定存在一个点设为a连接了v，同理也存在一个点设为b连接了a，同理也存在一个点设为c连接了b，同理…作为无环图，这个过程一定会在一个点停下，终止点的入度必须为0，所以u->…->c->b->a->v。由于v是随机选取的，所以u可以到达其他所有节点。

有了这个结论之后，在check时只需要先缩点然后更新每个scc的入度，统计入度为0的个数cnt，如果cnt等于1，那么返回true。

最终的思路是：读入边时将其存好，然后在0到最大边权的范围内对边权进行二分答案。每次check时建图，对于check的权值w，是反转边中权值最大的，所以小于等于w的边可以自由选择方向，相当于无向边，于是在建图时就可以直接建双边。大于w的建单边。然后进行缩点，判断入度为0的点的个数。

check的时间复杂度为O(n+m)，整体复杂度为O((n+m)logW)，W为最大边权

代码：

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineinf1e18constintN=2e5+5;intdfn[N],low[N],stk[N];intscc[N],in[N],ins[N];intid,tp,ti,n,m;vector<vector<int>>adj;structedge{intu,v;intw;};vector<edge>ed;voiddfs(intu)//缩点模版{dfn[u]=low[u]=++ti;stk[++tp]=u;ins[u]=1;for(intv:adj[u]){if(!dfn[v]){dfs(v);low[u]=min(low[u],low[v]);}elseif(ins[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){id++;do{intv=stk[tp];scc[v]=id;ins[v]=0;}while(stk[tp--]!=u);}}boolcheck(intw){adj.clear();//每次建图前先清空之前的数据adj.resize(n+1);for(inti=0;i<m;i++){intu=ed[i].u;intv=ed[i].v;if(ed[i].w<=w)//小于等于w的边可以自由选择方向,相当于无向边{adj[u].push_back(v);adj[v].push_back(u);}elseadj[u].push_back(v);}for(inti=1;i<=n;i++){dfn[i]=low[i]=stk[i]=0;scc[i]=in[i]=ins[i]=0;id=tp=ti=0;}for(inti=1;i<=n;i++){if(!dfn[i])dfs(i);}for(intu=1;u<=n;u++)//统计入度{inta=scc[u];for(intv:adj[u]){intb=scc[v];if(a==b)continue;in[b]++;}}intcnt=0;for(inti=1;i<=id;i++){if(in[i]==0)cnt++;}returncnt==1;}voidsolve(){cin>>n>>m;intu,v,w,l=0,r=0;for(inti=0;i<m;i++){cin>>u>>v>>w;ed.push_back({u,v,w});r=max(r,w);}if(!check(r))//当check的w是最大的边权的表示任何边都可以自由选择方向{cout<<-1<<endl;//如果返回false,那么无论如何都完不成任务return;}if(check(l))//当check的w为0时表示任何边都不能反转{cout<<0<<endl;//如果返回true,说明不需要反转任何边就能完成任务,代价为0return;}while(l<r){intmid=l+r>>1;if(check(mid))r=mid;elsel=mid+1;}cout<<r<<endl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT=1;cin>>T;while(T--){solve();ed.clear();}return0;}