Lvat_s Blog

首先最大值最小显然是二分

然后就是混合图的欧拉回路

首先我们对于无向图的欧拉回路可以记录点的度数(度数为偶数)，有向图的欧拉回路则是Abs(入度-出度)为偶数时有欧拉回路

那么混合图怎么办？网络流判定就好了。

为了方便和卡常数我所有的流量都除以了2.

我们把无向边随便定个方向再计算出度和入度，然后再连接一条反向边流量为1表示可以返回(因为可能无向边定的方向是相反的，那么对入度和出度会造成总共2的影响，所以连接流量为1)

然后对于入度>出度的点，我们连接源点到这个点，流量是入度减去出度再除以2.

否则连接这个点到汇点，流量是出度减去入度再除以2.

那么判断这个图是否满流就知道能不能形成欧拉回路了(因为欧拉回路每条边都经过所以一定满流)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=2005,INF=2100000000;

int n,m,h[N],level[N],S,T,cur[N],in[N],out[N],en;
queue<int> Q;

struct E{
int u,v,a,b;
}es[N];

struct Edge{
int b,f,back,next;
}e[N<<2];

int Abs(int x){return x>0?x:-x;}

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
Q.push(S);
level[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f==0)return flow;
    }
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=n+2;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}

bool Odd(){for(int i=1;i<=n;i++)if(Abs(in[i]-out[i])&1)return 1;return 0;}

bool Test(int k){
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(h,0,sizeof(h));
en=0;S=n+1;T=n+2;
for(int i=1;i<=m;i++){
	if(es[i].a<=k && es[i].b<=k)AddEdge(es[i].v,es[i].u,1),out[es[i].u]++,in[es[i].v]++;
	else if(es[i].a<=k)out[es[i].u]++,in[es[i].v]++;
	else if(es[i].b<=k)out[es[i].v]++,in[es[i].u]++;
	else return 0;
}
if(Odd())return 0;
int ank=0;
for(int i=1;i<=n;i++){
	if(in[i]>out[i])AddEdge(S,i,in[i]-out[i]>>1),ank+=in[i]-out[i]>>1;
    if(in[i]<out[i])AddEdge(i,T,out[i]-in[i]>>1);
}
return Dinic()==ank;
}

int main(){
freopen("2095.in","r",stdin);
freopen("2095.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d %d %d %d",&es[i].u,&es[i].v,&es[i].a,&es[i].b);
int l=1,r=1000,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Test(mid))r=mid-1,ans=mid;
    else l=mid+1;
}
if(!ans)puts("NIE");
else printf("%d\n",ans);
return 0;
}