题解【[POI2010]MOS-Bridges】

传送门。

$\texttt{Description}$

每条边正向和反向有两个权值，求最大边权尽量小的欧拉回路。

$1\le n\le 10^3$，$1\le m\le 2\times 10^3$。

$\texttt{Solution}$

前置芝士。

一道题，没有烟，一道毒瘤调一天。

聪明的你学会了前置芝士，知道了无解的一个充分条件是，每个点的入度都为偶数。

看到最大边权尽量小，条件反射出二分答案。

我们就不妨二分最大的边权 $k$，那么原图中边权大于 $k$ 的边都不用管。

看到 $n,m$ 稍大，考虑构建一个二分图：左边是边，右边是点。

我们寄 $in_i$ 表示 $i$ 点的入度，显然 $in_i$ 是偶数。

则到达这个点边的数量一定等于从这个点出发的边的数量。

所以从 $i$ 点流出的流量，即流向 $t$ 的流量，一定是 $\frac{in_i}{2}$，有一半是流入的。

根据欧拉回路的定义，每一条边只能匹配一次，所以可以把 $s$ 向每一条边连一条容量为 $1$ 的边。

边和点的连边也很简单了，我们对于原图的一条边 $(u,v,w_1,w_2)$，如果 $w_1\le k$，则 $u$ 可以到达 $v$，也就是说这条边可以流到 $v$ 这里。则这条边向 $v$ 连一条容量为 $1$ 的边。$w_2$ 的情况也同理。

跑一遍最大流，只需要判断最大流是否满流即可。也就是 $\frac{1}{2}\sum in_i$。

对于输出方案，我们枚举每一条边 $i$，如果 $i\to v_i$ 的残余流量为 $0$，说明这条边是选择的，也就是 $u_i\to v_i$ 是被选择的，直接建一张新图，把这条边加进去就行了；$i\to u_i$ 残余流量为 $0$ 的情况也一样。

最后只需要在新图中找一条欧拉路径，模板题了吧。。。。。

核心代码：

inline void remake()
{
    Clear(head),Clear(edge);
    tot=1;
    return;
}
int in[MAXN];
inline bool check(int k)
{
    remake();
    int all(0);
    rep(i,1,n) add_edge(i+m,t,in[i]>>1),all+=(in[i]>>1);
    rep(i,1,m)
    {
        add_edge(s,i,1);
        if(a[i].w1<=k) add_edge(i,a[i].y+m,1);
        if(a[i].w2<=k) add_edge(i,a[i].x+m,1);
    }
    int ans(0);
    while(bfs()) ans+=dfs(s,INF);
    return ans==all;
}
int out[MAXN],p;
bool vis[MAXN];
inline void Find(int u,int lst)
{
    while(head2[u])
    {
        E e=edge2[head2[u]];
        head2[u]=e.nxt;
        Find(e.to,e.flow);
    }
    if(lst) out[++p]=lst;
}
int main()
{
    n=read(),m=read();
    s=0,t=n+m+1;
    rep(i,1,m) 
    {
        a[i].x=read(),a[i].y=read(),a[i].w1=read(),a[i].w2=read();
        ++in[a[i].x],++in[a[i].y];
    }
    rep(i,1,n) if(in[i]&1)
    {
        puts("NIE");
        return 0;
    }
    int l=1,r=1000,res(-1);
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,res=mid;
        else l=mid+1;
    }
    if(res==-1)
    {
        puts("NIE");
        return 0;
    }
    printf("%d\n",res);
    check(res);
    rep(i,1,m)
        gra(j,i)
        {
            E e=edge[j];
            if(e.to!=s&&(!e.flow))
            {
                if(e.to-m==a[i].y) add_edge2(a[i].x,a[i].y,i);
                else add_edge2(a[i].y,a[i].x,i);
            }
        }
    Find(1,0);
    rep(i,1,p) printf("%d ",out[p-i+1]);
    return 0;
}

$$\texttt{The End.by UF}$$