YbtOJ 584「网络流」欧拉回路
题目链接：YbtOJ #584
小 A 有一张 n 个点 m 条边的图，每条边正走与逆走有着不同的边权。
定义一张图的欧拉回路为经过图中每条边恰好一次，且起点与终点相同的一条路径。（注意，尽管本题中每条边正走与逆走有不同的边权，但 仍然是一条边，即正走与逆走次数之和应恰好为 1）
小 A 想要知道所有欧拉回路中 所经最大边权 的最小值，并希望你给出任意一条所经最大边权最小的欧拉回路。
2leq nleq 1000，1leq mleq 2000，1le边权le10^3。
Solution
很容易想到二分答案 mid。
如果正反向仅有一个 边权 ge mid，则直接连上，如果两个都 ge mid，则先随便定个向。
统计每个点 Delta i = 入读 - 出度，如果是欧拉回路的充要条件是 forall i,Delta i =0。
一开始随便定向的边可以翻转，会导致 Delta x ,Delta y 减小 2，增大 2。
于是我们可以让所有 Delta i > 0Delta i <01 的边。
只需要跑一次网络流，如果满流则存在欧拉回路。
方案输出只需要根据网络流满流情况定个向然后随便跑一下就行了。
Code
代码语言：javascript复制#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=1e3 10,M=2e4 10,inf=2e9;
int n,m,in[N],out[N],S,T,vis[M],cnt,g[N];
struct Edge{int x,y,v1,v2;}e[M];
namespace Flow{
int fir[N],nxt[(M N)<<1],son[(M N)<<1],w[(M N)<<1],tot,cur[N],dis[N];
I void Add(CI x,CI y,CI z){nxt[ tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,nxt[ tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0;}
#define to son[i]
queue<int> q;
I bool bfs(){W(!q.empty()) q.pop();q.push(S);memset(dis,-1,sizeof(dis));dis[S]=0;W(!q.empty()){RI u=q.front(),i;q.pop();for(i=fir[u];i;i=nxt[i]) if(w[i]>0&&dis[to]==-1) dis[to]=dis[u] 1,q.push(to);}return ~dis[T];}
I int dfs(CI x,CI flow){if(x==T) return flow;RI i,d,now=flow;for(i=cur[x];i;i=nxt[i]) if(cur[x]=nxt[i],w[i]>0&&dis[to]==dis[x] 1){d=dfs(to,min(w[i],now));w[i]-=d,w[i^1] =d,now-=d;if(!now) break ;}return flow-now;}
I int F(){RI i,Ans=0;W(bfs()){for(i=1;i<=cnt;i ) cur[i]=fir[i];Ans =dfs(S,inf);}return Ans;}
I void C(){memset(fir,0,sizeof(fir)),tot=1;}
}
I bool chk(CI x){
memset(in,0,sizeof(in)),memset(out,0,sizeof(out)),Flow::C(),cnt=n,S= cnt,T= cnt;RI i,X=0;for(i=1;i<=m;i ) max(e[i].v1,e[i].v2)<=x?out[e[i].x] ,in[e[i].y] ,Flow::Add(e[i].y,e[i].x,1),0:e[i].v1<=x?out[e[i].x] ,in[e[i].y] :e[i].v2<=x&&(out[e[i].y] ,in[e[i].x] );
for(i=1;i<=n;i ) if(abs(in[i]-out[i])&1) return 0;else in[i]>out[i]&&(Flow::Add(S,i,abs(in[i]-out[i])>>1),X =abs(in[i]-out[i])>>1),in[i]<out[i]&&(Flow::Add(i,T,abs(in[i]-out[i])>>1),0);return Flow::F()==X;
}
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<PA> G[N];
vector<int> stk;
#define pb push_back
I void Add(CI x,CI y,CI z){G[x].pb(MP(y,z));}
I void DFS(CI x){PA i;for(RI j=0;j<G[x].size();j=max(j 1,g[x])) if(i=G[x][j],!vis[i.se]) vis[i.se]=1,g[x]=j 1,DFS(i.fi),stk.pb(i.se);}
I void Prt(CI X){RI i,j;for(assert(chk(X)),i=1,j=2;i<=m;i ) max(e[i].v1,e[i].v2)<=X?(Flow::w[j]?Add(e[i].x,e[i].y,i):Add(e[i].y,e[i].x,i),j =2):e[i].v1<=X?Add(e[i].x,e[i].y,i),0:(e[i].v2<=X&&(Add(e[i].y,e[i].x,i),0));for(i=1;i<=n;i ) sort(G[i].begin(),G[i].end());DFS(1);}
I void Out(){reverse(stk.begin(),stk.end());for(auto i:stk) write(i),pc(' ');pc('n');}
int main(){
freopen("euler.in","r",stdin),freopen("euler.out","w",stdout);
RI i,l=0,r=1000,mid,X=2e9;for(srand(time(NULL)),srand(rand()),srand(rand()),read(n,m),i=1;i<=m;i ) read(e[i].x,e[i].y,e[i].v1,e[i].v2),l=max(l,min(e[i].v1,e[i].v2)),r=max(r,max(e[i].v1,e[i].v2));
W(l<=r) chk(mid=l r>>1)?X=mid,r=mid-1:l=mid 1;return X>=2e9?puts("NIE"):(writeln(X),Prt(X),Out(),0),clear(),0;
}
