Question:
给一n个节点m条边的有向有权图 现可以改变其中一些边的方向 总代价是这些边的最大值,问使该图无环的最小花费 n,m<1e5
Solution:
由于代价为所有边的最大值,想到二分
然后对所有大于mid的边进行拓扑排序后,如果没有环那mid这个值就是可行的。
并且把不在图中的边(即权值小于mid)并且top【u】>top【v】的边翻转即可
#include<bits/stdc++.h>
#define rep(i,a,b) for(LL i=(a);i<=(b);i++)
#define per(i,a,b) for(LL i=(a);i>=(b);i--)
#define warn printf("!!!***!\n")
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VL;
const int maxn=3e5+6;
const int oo=0x3fffffff;
const int mod=1e9+7;
const double pi=acos(-1);
///head
int n,m,cnt=0,top[maxn],in[maxn],p[maxn];
struct node
{
int u,v,w;
}a[maxn];
VI vec[maxn];
queue<int>q;
bool ok(int mid)
{
rep(i,1,n) vec[i].clear(),top[i]=in[i]=0;
rep(i,1,m){
if(a[i].w>mid) vec[a[i].u].pb(a[i].v),in[a[i].v]++;
}
while(!q.empty()) q.pop();
rep(i,1,n){
if(in[i]==0) q.push(i);
}
int c=0;
while(!q.empty()){
int f=q.front();q.pop();
top[f]=++c;
rep(i,0,SZ(vec[f])-1){
int y=vec[f][i];
in[y]--;
if(!in[y]) {
q.push(y);
//top[y]=top[f]+1;
}
}
}
rep(i,1,n) if(in[i]) return 0;
cnt=0;
rep(i,1,m){
if(a[i].w<=mid){
if(top[a[i].u]>top[a[i].v]) p[++cnt]=i;
}
}
return 1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
rep(i,1,m){
cin>>a[i].u>>a[i].v>>a[i].w;
}
int l=0,r=1e9,ans=1e9;
while(l<=r){
int mid=l+r>>1;
if(ok(mid)) {
r=mid-1;
ans=min(ans,mid);
}
else l=mid+1;
}
cout<<ans<<' '<<cnt<<'\n';
rep(i,1,cnt) cout<<p[i]<<' ';
cout<<'\n';
}