题目链接

\(Solution\)

看到"最大值最小"，就知道应该要二分

二分之后，对于每个\(mid\),只要计算小于\(mid\)的边，然后在剩下的图中判断有无欧拉回路

但这个图是一个混合图.

先对每条无向边随意的定向，统计每个点入度和出度的差，如果有一个点的入度和出度的奇偶性不同，那么就肯定无解（而改变无向边方向的话，会让它们的入读\(-\)出度变化\(2\)，则他们的差无法变为\(0\),所以无法相同）

如果入度\(-\)出度\(=x\)，若\(x < 0\),就向\(t\)连一条\(abs(x/2)\) 的边，否则就从源点连一条\(abs(x/2)\)的边，对于原来定向的无向边\((a,b)\),建立一条从\(b\)到\(a\)，容量为\(1\)(这个表示的意义时将\(a->b\)这一条边变成了从\(b->a\))

流一条流就代表将一条无向边反向

如果满流则存在欧拉回路

\(Code\)

#include
    
     #define rg register#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);using namespace std;const int inf=1e9;int read(){    int x=0,f=1;    char c=getchar();    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();    return f*x;}struct node{    int to,next,v;}a[200001];int head[20001],cnt=1,n,m,s,t,x,y,z,minx,maxx,dep[20001];void add(int x,int y,int c){    a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,head[x]=cnt;    a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,head[y]=cnt;}queue
     
       q;int bfs(){    memset(dep,0,sizeof(dep));    q.push(s);    dep[s]=1;    while(!q.empty()){        int now=q.front();        q.pop();        for(int i=head[now];i;i=a[i].next){            int v=a[i].to;            if(!dep[v]&&a[i].v>0)                dep[v]=dep[now]+1,q.push(v);        }    }    if(dep[t])        return 1;    return 0;}int dfs(int k,int list){    if(k==t||!list)        return list;    for(int i=head[k];i;i=a[i].next){        int v=a[i].to;        if(dep[v]==dep[k]+1&&a[i].v>0){            int p=dfs(v,min(list,a[i].v));            if(p){                a[i].v-=p;        a[i^1].v+=p;                return p;            }        }    }    return dep[k]=0;}int Dinic(){    int ans=0,k;    while(bfs())        while((k=dfs(s,inf)))            ans+=k;    return ans;}int A[20001],B[20001],C[20001],D[20001],vis[10001],tot;bool build(int x){    memset(head,0,sizeof(head));    memset(vis,0,sizeof(vis));    s=0,t=n+1,cnt=1,tot=0;    for(int i=1;i<=m;i++){        if(C[i]<=x) vis[A[i]]--,vis[B[i]]++;        if(D[i]<=x) add(B[i],A[i],1);    }    for(int i=1;i<=n;i++)        if(vis[i]&1)            return 0;    for(int i=1;i<=n;i++){        if(vis[i]>0)            tot+=vis[i]/2,add(s,i,vis[i]/2);        else add(i,t,-vis[i]/2);    }    return 1;}bool check(int x){    bool res=build(x);    if(!res) return 0;    return Dinic()==tot;}int main(){    n=read(),m=read(),minx=2147483647,maxx=0;    for(int i=1;i<=m;i++){        A[i]=read(),B[i]=read(),C[i]=read(),D[i]=read();            if(C[i]>D[i])        swap(A[i],B[i]),swap(C[i],D[i]);        minx=min(C[i],minx),maxx=max(maxx,D[i]);        }    int l=minx,r=maxx,ans=0;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid))            r=mid-1,ans=mid;        else l=mid+1;    }    if(!ans) puts("NIE"),exit(0);    printf("%d",ans);    return 0;}