题意

一个 \(n\) 个点 \(m\) 条边的图，每条边双向都有权值（可能不一样）。求从 1 开始，经过所有点，经过所有边一次且仅一次（即一定要经过这条边的某个方向）回到 1 的路径上权值最大的最小是多少。\(n\le 1000,m\le 2000\) 。

分析

显然二分答案，判定是否存在欧拉回路。

欧拉回路的判定用网络流方法。

若是一个有向图，存在欧拉欧拉回路的充要条件是每个点入度等于出度。但这是一个混合图，含有无向边，所以我们要看看无向边走哪个方向，使得每个点的入度等于出度。

对于一条无向边，任意定向，先判断每个点的入度出度之差是否是偶数。若不是，那么无论如何更改方向都不能满足条件。若是偶数，这实际上就告诉我们，每个点有多少入度或者出度需要更改。

设 \(d_x\) 为 \(x\) 点的入度减出度，那么若 \(d_x>0\) ，向汇点连 \(\frac{d_x}{2}\) 的边，否则从源点连 \(\frac{|d_x|}{2}\) 的边。对于任意定向的无向边，给 1 的容量。

考虑这个网络上的一条增广路，它的含义是把这个路径上的边全部反向。注意，这只影响了开头的点和末尾的点的入度与出度关系。具体来说，起始点的入度加一，出度减一；末尾点的入度减一，出度加一。若源点出边满流，就说明，每个点的不合法出度已经被全部更改完了，那么每个点的不合法出度也相应地更改完了。也就是说，原来任意定向的边有 1 的流量，那么把这条边反过来，这样构造的新图是满足每个点的入度等于出度的，即存在欧拉回路。

复杂度为 \(O(n^2m\log w)\) 。

UPD: 这题的可二分性有待讨论，搞不好这题是错的。

代码

#include<bits/stdc++.h>

#define M(x) memset(x,0,sizeof x)

using namespace std;

inline char nchar() {

	static const int bufl=1<<20;

	static char buf[bufl],*a,*b;

	return a==b && (b=(a=buf)+fread(buf,1,bufl,stdin),a==b)?EOF:*a++;

}

inline int read() {

	int x=0,f=1;

	char c=nchar();

	for (;!isdigit(c);c=nchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=nchar()) x=x*10+c-'0';

	return x*f;

}

const int maxn=1e3+10;

const int maxm=4e3+10;

template<typename T> inline void Max(T &x,T y) {x=max(x,y);}

int n,m,f[maxn],all,ind[maxn],oud[maxn];

int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}

struct bian {

	int x,y,a,b;

} b[maxm];

struct some {

	int x,y;

	bool bi; // true: undir; false: dir

} a[maxm];

namespace graph {

	struct edge {

		int v,w,nxt;

	} e[maxm];

	int h[maxn],tot,que[maxn],ql,qr,d[maxn];

	inline void clear() {

		memset(h,-1,sizeof h);

		tot=1;

	}

	inline void add(int x,int y,int w) {

		e[++tot]=(edge){y,w,h[x]};

		h[x]=tot;

		e[++tot]=(edge){x,0,h[y]};

		h[y]=tot;

	}

	inline bool bfs(int s,int t) {

		memset(d,0,sizeof d);

		d[que[ql=qr=1]=s]=1;

		while (ql<=qr) {

			int x=que[ql++];

			for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (e[i].w && !d[v]) d[que[++qr]=v]=d[x]+1;

		}

		return d[t];

	}

	int dfs(int x,int t,int mi) {

		if (x==t) return mi;

		int flow=0;

		for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (e[i].w && d[v]==d[x]+1) {

			int tmp=dfs(v,t,min(mi,e[i].w));

			if (!tmp) {d[v]=0;continue;}

			e[i].w-=tmp,e[i^1].w+=tmp,mi-=tmp,flow+=tmp;

			if (!mi) break;

		}

		return flow;

	}

	inline int maxflow(int s,int t) {

		int ret=0;

		while (bfs(s,t)) ret+=dfs(s,t,INT_MAX);

		return ret;

	}

}

inline bool check() {

	M(ind),M(oud);

	for (int i=1;i<=all;++i) ++ind[a[i].y],++oud[a[i].x];

	for (int i=1;i<=n;++i) if ((ind[i]-=oud[i])&1) return false; else ind[i]>>=1;

	int S=0,T=n+1,sm=0;

	graph::clear();

	for (int i=1;i<=all;++i) if (a[i].bi) graph::add(a[i].x,a[i].y,1);

	for (int i=1;i<=n;++i) if (ind[i]>0) graph::add(i,T,ind[i]); else if (ind[i]<0) graph::add(S,i,-ind[i]),sm-=ind[i];

	int flow=graph::maxflow(S,T);

	return flow==sm;

}

inline bool ok(int mx) {

	for (int i=1;i<=n;++i) f[i]=i;

	int cnt=n;

	for (int i=1;i<=m;++i) if (b[i].a<=mx || b[i].b<=mx) {

		int fx=find(b[i].x),fy=find(b[i].y);

		if (fx!=fy) f[fx]=fy,--cnt;

	}

	if (cnt>1) return false;

	all=0;

	for (int i=1;i<=m;++i) if (b[i].a<=mx && b[i].b<=mx) a[++all]=(some){b[i].x,b[i].y,true}; else {

		if (b[i].a<=mx) a[++all]=(some){b[i].x,b[i].y,false};

		if (b[i].b<=mx) a[++all]=(some){b[i].y,b[i].x,false};

	}

	return check();

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	int l=1,r=0,ans;

	n=read(),m=read();

	for (int i=1;i<=m;++i) b[i].x=read(),b[i].y=read(),b[i].a=read(),b[i].b=read(),Max(r,max(b[i].a,b[i].b));

	while (l<=r) {

		int mid=l+r>>1;

		if (ok(mid)) ans=mid,r=mid-1; else l=mid+1;

	}

	ans?printf("%d\n",ans):puts("NIE");

	return 0;

}