E. Andrew and Taxi

Andrew and Taxi"/>

E. Andrew and Taxi

题目链接
E. Andrew and Taxi

题意:

给定一个带权有向图，你可以选择一个 x x x，令权值小于等于 x x x边的方向反转，或者不变，使最后图中没有环。

思路

考虑对于权值大于 x x x的边，如果这些边组成的图有环，则不满住题意。
找到一个最小的 x x x，大于的没有环，我们可以让小于 x x x的，边 ( u , v ) (u,v) (u,v)，的方向为：拓朴序小的连向大的，不会形成环。

代码：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5+10;
int h[N],e[N],ne[N],w[N],idx;
int n,m;
struct node{int u,v,w;
}edge[N];
void add(int a,int b,int c){ne[idx] = h[a],e[idx] = b,w[idx] = c,h[a] = idx++;
}
int in[N],scc[N],tim;
bool check(int mid){queue<int> q;tim = 0;for(int i = 1;i<=n;i++)in[i] = 0,scc[i] = 0;for(int i = 0;i<idx;i++)if(w[i] > mid)in[e[i]]++;for(int i = 1;i<=n;i++)if(!in[i])q.push(i),scc[i] = ++tim;while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i=ne[i]){if(w[i] > mid && -- in[e[i]] == 0)q.push(e[i]),scc[e[i]] = ++tim;}}for(int i = 0;i<idx;i++)if(w[i] > mid && in[e[i]])return false;return true;
}int main(){cin >> n >> m;memset(h,-1,sizeof h);for(int i = 1,a,b,c;i<=m;i++){cin >> a >> b >> c;edge[i]={a,b,c};add(a,b,c);}int l = 0,r = 1e9;while(l < r){int mid = l + r >> 1;if(check(mid))r = mid;else l = mid + 1;}check(l);vector<int> res;for(int i = 1;i<=m;i++){if(edge[i].w <= l){int u = edge[i].u,v = edge[i].v;if(scc[u] > scc[v])res.push_back(i);}}printf("%d %d\n",l,res.size());for(auto s:res)printf("%d ",s);return 0;
}