题解：Edge Reverse

发布时间：2026/7/24 19:37:55

题目https://codeforces.com/problemset/problem/1777/E我的最初想法是先进行缩点然后加入剩余的边忽略边的方向因为剩余的边都可以调整方向用并查集维护连通性只要有一个点没有加入并查集说明有不止一个连通块那么就直接输出-1。然后特判完后可以考虑二分答案然后就卡住了不知道怎么check。此题的关键点在于缩点后的图是一个有向无环图(DAG)在DAG上存在一个节点能到达其他所有节点的充要条件是只有一个入度为0的点且能到达其他所有节点的点即是该入度为0的点证明充分性在DAG上存在一个节点能到达其他所有节点那么只有一个入度为0的点。反证法假设该点为u入度不为0那么肯定存在一个节点设为v连接了u而u可以到达所有节点u能到达vv又能到达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(nm)整体复杂度为O((nm)logW)W为最大边权代码#includebits/stdc.husingnamespacestd;#defineintlonglong#defineinf1e18constintN2e55;intdfn[N],low[N],stk[N];intscc[N],in[N],ins[N];intid,tp,ti,n,m;vectorvectorintadj;structedge{intu,v;intw;};vectoredgeed;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{intvstk[tp];scc[v]id;ins[v]0;}while(stk[tp--]!u);}}boolcheck(intw){adj.clear();//每次建图前先清空之前的数据adj.resize(n1);for(inti0;im;i){intued[i].u;intved[i].v;if(ed[i].ww)//小于等于w的边可以自由选择方向,相当于无向边{adj[u].push_back(v);adj[v].push_back(u);}elseadj[u].push_back(v);}for(inti1;in;i){dfn[i]low[i]stk[i]0;scc[i]in[i]ins[i]0;idtpti0;}for(inti1;in;i){if(!dfn[i])dfs(i);}for(intu1;un;u)//统计入度{intascc[u];for(intv:adj[u]){intbscc[v];if(ab)continue;in[b];}}intcnt0;for(inti1;iid;i){if(in[i]0)cnt;}returncnt1;}voidsolve(){cinnm;intu,v,w,l0,r0;for(inti0;im;i){cinuvw;ed.push_back({u,v,w});rmax(r,w);}if(!check(r))//当check的w是最大的边权的表示任何边都可以自由选择方向{cout-1endl;//如果返回false,那么无论如何都完不成任务return;}if(check(l))//当check的w为0时表示任何边都不能反转{cout0endl;//如果返回true,说明不需要反转任何边就能完成任务,代价为0return;}while(lr){intmidlr1;if(check(mid))rmid;elselmid1;}coutrendl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT1;cinT;while(T--){solve();ed.clear();}return0;}