i207M给的题
给定一张有向图，每条边有边权。你可以花费边权的代价反转一条边，使得原图中没有环。最小化反转的边权的最大值。
首先二分，然后考虑判定。
转化为有些边可以翻转，有些边不可以翻转，使得图中没有环
我们把不能反向的边拿出来，然后跑拓扑排序判环，如果有环则无解，不然一定有一种方案，加入那些可以改变方向的边而不产生环。
新加的边方向：拓扑序小的连向拓扑序大的
有环一定是大的拓扑序连向小的拓扑序有一条边
而这样是一定没有环的！
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
int n,m;
struct edge{
int x,y,z;
}b[N];
struct node{
int nxt,to;
}e[*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int dfn[N],df;
int q[N],l,r;
int du[N];
int mem[N],tot;
bool topo(){
memset(dfn,,sizeof dfn);
l=,r=;
df=;
for(reg i=;i<=n;++i){
if(du[i]==){
q[++r]=i;
dfn[i]=++df;
}
}
while(l<=r){
int x=q[l++];
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
du[y]--;
if(!du[y]){
dfn[y]=++df;
q[++r]=y;
}
}
}
for(reg i=;i<=n;++i){
if(!dfn[i]) return false;
}
return true;
}
bool che(int mid){
memset(du,,sizeof du);
memset(hd,,sizeof hd);
cnt=;
for(reg i=;i<=m;++i){
if(b[i].z>mid){
add(b[i].x,b[i].y);
++du[b[i].y];
}
}
return topo();
}
int main(){
rd(n);rd(m);
int x,y,z;
int L=,R=;
for(reg i=;i<=m;++i){
rd(x);rd(y);rd(z);R=max(R,z);
b[i].x=x;b[i].y=y;b[i].z=z;
}
int ans=;
while(L<=R){
int mid=(L+R)>>;
if(che(mid)){
ans=mid;R=mid-;
}else L=mid+;
}
printf("%d ",ans);
bool haha=che(ans);
for(reg i=;i<=m;++i){
if(dfn[b[i].x]>dfn[b[i].y]){
mem[++tot]=i;
}
}
sort(mem+,mem+tot+);
printf("%d\n",tot);
for(reg i=;i<=tot;++i){
printf("%d ",mem[i]);
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/1/16 11:46:04
*/