题目分析

题意理解

我们有一个无向图，但每条边实际上是有向的（两个方向权值不同）。需要找到一条从1号点出发，经过所有边恰好一次并回到1号点的回路（欧拉回路），使得路径中经过的边的最大权值最小。

关键点

1. 欧拉回路存在条件：所有顶点的入度等于出度
2. 边方向选择：对于每条边，我们可以选择 a→b 或 b→a 的方向
3. 最小化最大值：需要最小化路径中出现的最大边权

算法思路

整体框架

使用二分答案 + 网络流的框架：

1. 二分最大权值：在 [0, 1000] 范围内二分
2. 可行性检查：对于每个候选值 mid，检查是否存在欧拉回路使得所有边权 ≤ mid
3. 构造解：找到最小可行值后，构造具体的欧拉回路

可行性检查（核心算法）

对于给定的 mid：

1. 边分类：

   • 如果两个方向权值都 > mid：直接不可行
   • 如果只有一个方向 ≤ mid：强制选择该方向
   • 如果两个方向都 ≤ mid：方向待定

2. 度数计算：

   • 初始化每个顶点的出度减入度 deg[i]
   • 对于强制方向的边，更新度数
   • 对于待定方向的边，暂时假设从 a→b，更新度数

3. 网络流建模：

   • 源点向 deg[i] > 0 的点连边，容量为 deg[i]/2
   • deg[i] < 0 的点向汇点连边，容量为 -deg[i]/2
   • 对于待定方向的边 (a,b)，从 a 向 b 连容量为1的边

4. 判断可行性：

   • 检查所有 |deg[i]| 是否为偶数
   • 检查源点出边总容量是否等于汇点入边总容量
   • 跑最大流，如果满流则可行

构造欧拉回路

利用网络流结果确定待定边的方向，然后使用 Hierholzer 算法找欧拉回路。

代码详解

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)

// Dinic 最大流算法
struct Dinic {
    struct Edge {
        int to, rev;
        long long cap, flow;
    };
    vector<int> lvl, nxt, q;
    vector<vector<Edge>> adj;
    
    Dinic(int n) : lvl(n), nxt(n), q(n), adj(n) {}
    
    void addEdge(int a, int b, long long cap) {
        adj[a].pb({b, (int)adj[b].size(), cap, 0ll});
        adj[b].pb({a, (int)adj[a].size() - 1, 0ll, 0ll});
    }
    
    long long dfs(int a, int t, long long f) {
        if (a == t || !f) return f;
        
        for (int &i = nxt[a]; i < (int)adj[a].size(); i++) {
            Edge &e = adj[a][i];
            if (lvl[a] + 1 == lvl[e.to]) {
                if (long long p = dfs(e.to, t, min(f, e.cap - e.flow))) {
                    e.flow += p;
                    adj[e.to][e.rev].flow -= p;
                    return p;
                }
            }
        }
        return 0;
    }
    
    long long maxflow(int s, int t) {
        long long flow = 0;
        q[0] = s;
        
        // 使用容量缩放优化
        rep(L, 0, 31) do {
            lvl = nxt = vector<int>(q.size());
            int qi = 0, qe = lvl[s] = 1;
            
            while (qi < qe && !lvl[t]) {
                int a = q[qi++];
                for (Edge &e : adj[a]) {
                    if (!lvl[e.to] && (e.cap - e.flow) >> (30 - L)) {
                        q[qe++] = e.to;
                        lvl[e.to] = lvl[a] + 1;
                    }
                }
            }
            
            while (long long p = dfs(s, t, 1e18)) flow += p;
        } while (lvl[t]);
        
        return flow;
    }
};

// 寻找欧拉回路
vector<int> eulerWalk(vector<vector<pair<int, int>>> &gr, int nedges, int src = 0) {
    int n = gr.size();
    vector<int> D(n), its(n), eu(nedges), ret, s = {src};
    D[src]++; // 允许欧拉路径
    
    while (!s.empty()) {
        int x = s.back(), y, e, &it = its[x], end = gr[x].size();
        
        if (it == end) {
            ret.push_back(x);
            s.pop_back();
            continue;
        }
        
        tie(y, e) = gr[x][it++];
        
        if (!eu[e]) {
            D[x]--, D[y]++;
            eu[e] = 1;
            s.push_back(y);
        }
    }
    
    // 检查是否是有效欧拉回路
    for (int x : D)
        if (x < 0 || ret.size() != nedges + 1)
            return {};
    
    return {ret.rbegin(), ret.rend()};
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    // 存储边信息: (a, b, w1, w2)
    vector<tuple<int, int, int, int>> edges(m);
    rep(i, 0, m) {
        int a, b, w1, w2;
        cin >> a >> b >> w1 >> w2;
        a--; b--; // 转为0-index
        edges[i] = {a, b, w1, w2};
    }

    vector<int> deg(n); // 出度 - 入度
    
    // 检查给定mid是否可行
    auto works = [&](int mid) {
        vector<pair<int, int>> good; // 可自由选择方向的边
        fill(all(deg), 0);
        
        // 处理每条边
        for (auto [a, b, w1, w2] : edges) {
            if (w1 > mid && w2 > mid) 
                return false; // 两个方向都不可用
            else if (w2 > mid) 
                deg[a]++, deg[b]--; // 强制选择 a->b
            else if (w1 > mid) 
                deg[b]++, deg[a]--; // 强制选择 b->a
            else {
                deg[a]++, deg[b]--; // 暂时选择 a->b
                good.eb(a, b);      // 记录可自由选择的边
            }
        }
        
        // 构建网络流图
        Dinic flow(n + 2);
        int source = n, sink = n + 1;
        int target0 = 0, target1 = 0;
        
        // 处理顶点度数约束
        rep(a, 0, n) {
            if (abs(deg[a]) & 1) 
                return false; // 度数必须为偶数
            else if (deg[a] >= 0) {
                flow.addEdge(source, a, abs(deg[a]) / 2);
                target0 += abs(deg[a]) / 2;
            } else if (deg[a] < 0) {
                flow.addEdge(a, sink, abs(deg[a]) / 2);
                target1 += abs(deg[a]) / 2;
            }
        }
        
        if (target0 != target1) return false;
        
        // 添加可自由选择的边
        for (auto [a, b] : good) 
            flow.addEdge(a, b, 1);
        
        // 检查是否满流
        long long mf = flow.maxflow(source, sink);
        return mf == target0;
    };
    
    // 二分查找最小可行值
    int l = 0, r = 1000 + 5, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (works(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    if (ans == -1) {
        cout << "NIE" << endl;
        return;
    } else {
        cout << ans << endl;
    }
    
    // 构造解
    int mid = ans;
    vector<vector<pair<int, int>>> g(n); // 邻接表: (邻居, 边索引)
    vector<tuple<int, int, int>> good;   // (a, b, 边索引)
    
    fill(all(deg), 0);
    
    // 重新处理边，构建图
    rep(i, 0, m) {
        auto [a, b, w1, w2] = edges[i];
        
        if (w1 > mid && w2 > mid) {
            // 不会发生，因为ans可行
        } else if (w2 > mid) {
            deg[a]++, deg[b]--;
            g[a].eb(b, i); // 强制 a->b
        } else if (w1 > mid) {
            deg[b]++, deg[a]--;
            g[b].eb(a, i); // 强制 b->a
        } else {
            deg[a]++, deg[b]--;
            good.eb(a, b, i); // 可自由选择
        }
    }
    
    // 构建网络流确定自由边的方向
    Dinic flow(n + 2);
    int source = n, sink = n + 1;
    int target0 = 0, target1 = 0;
    
    rep(a, 0, n) {
        if (deg[a] >= 0) {
            flow.addEdge(source, a, abs(deg[a]) / 2);
            target0 += abs(deg[a]) / 2;
        } else {
            flow.addEdge(a, sink, abs(deg[a]) / 2);
            target1 += abs(deg[a]) / 2;
        }
    }
    
    for (auto [a, b, idx] : good) 
        flow.addEdge(a, b, 1);
    
    flow.maxflow(source, sink);
    
    // 根据流结果确定自由边的方向
    set<pair<int, int>> flipped;
    rep(from, 0, n) {
        for (auto e : flow.adj[from]) {
            if (e.cap == 0 || from == source || e.to == sink || e.flow == 0) 
                continue;
            flipped.insert({from, e.to});
        }
    }
    
    // 构建最终图
    for (auto [a, b, idx] : good) {
        if (flipped.count({a, b})) 
            g[b].eb(a, idx); // 选择 b->a
        else 
            g[a].eb(b, idx); // 选择 a->b
    }
    
    // 构建边索引映射
    map<pair<int, int>, int> edgeIndex;
    rep(a, 0, n) {
        for (auto [b, idx] : g[a]) {
            edgeIndex[{a, b}] = idx;
        }
    }
    
    // 寻找欧拉回路
    auto path = eulerWalk(g, edgeIndex.size(), 0);
    
    // 输出边序列
    rep(i, 0, path.size() - 1) {
        cout << edgeIndex[{path[i], path[i + 1]}] + 1 << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();
    return 0;
}

算法核心要点

1. 网络流建模的巧妙之处

• 度数平衡：通过流来调整自由边的方向，使得所有顶点入度=出度
• 容量设置：每个顶点需要调整的度数为 |deg[i]|/2
• 自由边：容量为1，表示可以选择方向

2. 欧拉回路构造

• 使用 Hierholzer 算法
• 基于网络流确定的方向构建有向图
• 验证回路是否包含所有边

3. 复杂度分析

• 二分：O(log(1000)) ≈ 10 次
• 网络流：O((n+m)²) 但实际很快
• 欧拉回路：O(n+m)
• 总复杂度：能够处理 n=1000, m=2000 的数据

总结

这道题综合运用了：

1. 二分答案处理最小化最大值问题
2. 网络流处理度数约束和方向选择
3. 欧拉回路算法构造解
4. 图论建模将原问题转化为可行流问题

是一个很好的综合图论题目，考察了多种算法思想的结合运用。