题意
给一个边带权的有向图，可以花费边权使得一条边反向；通过翻转边让原图变成一个DAG，要求是所有花费中的最大值最小(,(n,mleq 200000))，保证无重边和自环
解法1
考场上没看出来性质，于是口胡了一个乱搞做法
连好边后直接对原图进行一遍拓扑排序，由于原图不是DAG，所以会有无法入队的环存在；如果当前队列为空而有点没有被遍历到，那么就强行选择一个点将连向它的边翻转；
具体的，我们选择((max() 连向(i)的边 ()))最小的(i)，由于翻转了连向(i)的边，需要将(ans)与((max() 连向i的边 ()))取最大值
维护max值用大根堆，维护max值最小的点用set，虽说复杂度为(O(nlogn))但并不好写（为什么还跑的比正解快啊qwq）
Code
#include<bits/stdc++.h>
#define N 200005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,m,rd[N],ans=0;
bool vis[N];
struct Edge
{
int next,to,dis;
}edge[N<<1];int head[N],cnt;
void add_edge(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
priority_queue<int> mx[N];//一个大根堆维护指向一个点最大的边权
priority_queue<int> lz[N];//一个大根堆懒删除
set< pair<int,int> > s;//一个set维护最大边权最小的点编号
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
void topo()//一次拓扑
{
queue<int> q;
for(int i=1;i<=n;++i)
if(!rd[i]) q.push(i);
else s.insert(make_pair(mx[i].top(),i));
int rest=n;
while(rest)
{
--rest;
int v,u;
if(q.empty())//成环了
{
v=s.begin()->first,u=s.begin()->second;
while(!s.empty()&&vis[u])
{
s.erase(make_pair(v,u));
v=s.begin()->first;u=s.begin()->second;
}
ans=Max(ans,v);
}
else {u=q.front();q.pop();}
vis[u]=1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(--rd[v]==0 && !vis[v]) {q.push(v);vis[v]=1;continue;}
//如果没有入队就更新
lz[v].push(edge[i].dis);//删除这条边
s.erase(make_pair(mx[v].top(),v));//更新最大值
while(!lz[v].empty()&&mx[v].top()==lz[v].top())
{
mx[v].pop();
lz[v].pop();
}
s.insert(make_pair(mx[v].top(),v));
}
}
}
int main()
{
freopen("pestc.in","r",stdin);
freopen("pestc.out","w",stdout);
read(n);read(m);
for(int i=1;i<=m;++i)
{
int x,y,z;
read(x);read(y);read(z);
add_edge(x,y,z);
mx[y].push(z);
++rd[y];
}
topo();
cout<<ans<<endl;
return 0;
}
解法2
题解做法
显然答案具有单调性，二分一个(mid)，将(leq mid)的边全部删掉，如果此时的图是一个DAG那么就返回true
正确性：由于此时的图是一个DAG，而(leq mid)的边方向可以随便定，从dfn小的点指向dfn大的点即可形成一个新的DAG
Code（CF1100E）
#include<bits/stdc++.h>
#define N 100005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,m,rd[N],ans=0;
int dfn[N],st[N],top;
struct Edge
{
int next,to,dis;
}edge[N<<1];int head[N],cnt;
void add_edge(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
bool topo(int mid)//检验能否完成一次拓扑
{
memset(rd,0,sizeof(rd));
memset(dfn,0,sizeof(dfn));
int tot=0;
for(int i=1;i<=n;++i)
for(int j=head[i];j;j=edge[j].next)
if(edge[j].dis>mid) ++rd[edge[j].to];
queue<int> q;
for(int i=1;i<=n;++i) if(!rd[i]) q.push(i);
while(!q.empty())
{
int u=q.front(); q.pop();
dfn[u]=++tot;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].dis<=mid) continue;
if(--rd[v]==0) q.push(v);
}
}
return (tot==n);
}
int main()
{
read(n);read(m);
for(int i=1;i<=m;++i)
{
int x,y,z;
read(x);read(y);read(z);
add_edge(x,y,z);
}
int l=0,r=1000000000;
while(l<=r)
{
int mid=(l+r)>>1;
if(topo(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
topo(ans);
for(int i=1;i<=n;++i)
for(int j=head[i];j;j=edge[j].next)
if(edge[j].dis<=ans&&dfn[i]>dfn[edge[j].to]) st[++top]=j;
printf("%d %d
",ans,top);
sort(st+1,st+top+1);
for(int i=1;i<=top;++i) printf("%d ",st[i]);
printf("
");
return 0;
}
原题CF1100E Andrew and Taxi还需要输出翻转边的方案，用解法2通过比较dfn可以很容易输出方案；而解法1还需要再在大根堆中记录每条边的编号emmm