【Codeforces Round #532 (Div. 2) E. Mahmoud and a xor trip】 二分+拓扑排序

E. Andrew and Taxi

题意

给你一个有边权的有向图，反转一条边的代价是这条边的边权，反转多个边的代价是所有反转边里面边权最大的那条边的边权，问让这个图不存在环的最小代价，以及被反转的边的编号。

做法

首先求最小代价，我们只需要二分这个代价，check就是看删除所有小于这个代价的边之后是否有环。
输出边集，要用到拓扑排序的一个性质
一个图进行拓扑排序后，对于每一个有向边u->v都存在u的拓扑序<v的拓扑序，则这个图上无环
之后我们就枚举所有小于当前代价的边，对所有不满足条件的边反转就可以。
这样就保证反转之后无环，而且代价最小。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 1e5+5;
#define Se second
#define Fi first
int n,m;
vector<pii> G[maxn];
int top[maxn];
int ind[maxn];
int que[maxn];
bool check(int mid)
{
    int qt=0;for(int i=1;i<=n;i++) ind[i]=0;for(int i=1;i<=n;i++){
    for(int j=0;j<G[i].size();j++){
    if(G[i][j].Se>mid) ind[G[i][j].Fi]++;}}for(int i=1;i<=n;i++){
    if(ind[i]==0){
    que[qt++]=i;top[i]=qt;}}for(int i=0;i<qt;i++){
    int u=que[i];for(int j=0;j<G[u].size();j++){
    if(G[u][j].Se<=mid) continue;if(--ind[G[u][j].Fi]==0){
    que[qt++]=G[u][j].Fi;top[G[u][j].Fi]=qt;}}}for(int i=1;i<=n;i++) if(ind[i]) return false;return true;
}
struct Edge
{
    int u,v,w;Edge(){
    }Edge(int uu,int vv,int ww){
    u=uu;v=vv;w=ww;}
}E[maxn];
vector<int> ans;
int main()
{
    scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){
    int u,v,w;scanf("%d%d%d",&u,&v,&w);G[u].push_back(pii(v,w));E[i]=Edge(u,v,w);}int l=0,r=1000000000,mid;while(l<=r){
    mid=(l+r)/2;if(check(mid)) r=mid-1;else l=mid+1;}check(l);for(int i=1;i<=m;i++){
    int fi=E[i].u;int to=E[i].v;if(E[i].w<=l&&top[fi]>top[to]) ans.push_back(i);}printf("%d %d\n",l,ans.size());for(int i=0;i<ans.size();i++){
    printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');}return 0;
}