Codeforces Round #532 (Div. 2) E. Andrew and Taxi(二分+拓扑排序)

时间:2021-08-18 01:14:42

题目链接:https://codeforces.com/contest/1100/problem/E

题意:给出 n 个点 m 条边的有向图,要翻转一些边,使得有向图中不存在环,问翻转的边中最大权值最小是多少。

题解:首先要二分权值,假设当前最大权值是 w,那么大于 w 的边一定不能翻转,所以大于 w 所组成的有向图不能有环,而剩下小于等于 w 的边一定可以构造出一个没有环的图(因为如果一条边正反插入都形成环的话,那么图里之前已经有环了),构造方法是把大于 w 的边跑拓扑序,然后小于等于 w 的边序号小的连向序号大的。

 #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define mp(a,b) make_pair(a,b)
#define pi acos(-1)
#define pii pair<int,int>
#define pb push_back
#define lowbit(x) ((x)&(-x))
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e5 + ;
const int maxm = 1e6 + ;
const ll mod = 1e9 + ; int n,m; struct edge {
int from,to,w;
}e[maxn]; vector<int>vec[maxn];
int vis[maxn];
bool flag; void dfs(int u,int mid) {
vis[u] = ;
for(int i = ; i < vec[u].size(); i++) {
int x = vec[u][i];
if(e[x].w <= mid) continue;
if(vis[e[x].to] == ) {
flag = false;
continue;
} else if(vis[e[x].to] == ) continue;
dfs(e[x].to,mid);
}
vis[u] = ;
} bool check(int mid) {
mst(vis, );
flag = true;
for(int i = ; i <= n; i++) {
if(vis[i] == ) dfs(i,mid);
}
return flag;
} vector<int>out;
int top[maxn], du[maxn]; int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
scanf("%d%d",&n,&m);
for(int i = ; i <= m; i++) {
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);
vec[e[i].from].push_back(i);
}
int l = , r = 1e9, ans = ;
while(l <= r) {
int mid = (l + r) >> ;
if(check(mid)) ans = mid, r = mid - ;
else l = mid + ;
}
for(int i = ; i <= m; i++)
if(e[i].w > ans) du[e[i].to]++;
queue<int>q;
int tot = ;
for(int i = ; i <= n; i++)
if(du[i] == ) q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
top[u] = ++tot;
for(int i = ; i < vec[u].size(); i++) {
int v = vec[u][i];
if(e[v].w <= ans) continue;
du[e[v].to]--;
if(du[e[v].to] == ) q.push(e[v].to);
}
}
for(int i = ; i <= m; i++)
if(e[i].w <= ans && top[e[i].from] > top[e[i].to]) out.push_back(i);
printf("%d %d\n",ans,out.size());
for(int i = ; i < out.size(); i++) printf("%d ",out[i]);
return ;
}