1 条题解

  • 1
    @ 2025-1-18 19:52:58
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <queue>
    using namespace std;
    const int N = 2e2 + 5, M = 2e4 + 5, INF = 1e9;
    int n, m, s, t, w[N], ans[M];
    
    int idx = 1, h[N];
    struct edge 
    {
        int to, nxt, val;
    } e[M << 1];
    void addEdge(int u, int v, int c) 
    {
        e[++idx] = (edge) 
        {
            v, h[u], c
        };
        h[u] = idx;
    }
    
    int dep[N], now[N];
    queue <int> q;
    bool BFS() 
    {
        memset(dep, 0, sizeof(dep));
    
        while (!q.empty())
            q.pop();
    
        dep[s] = 1, q.push(s);
        now[s] = h[s];
    
        while (!q.empty()) 
        {
            int u = q.front();
            q.pop();
    
            for (int i = h[u]; i; i = e[i].nxt) 
            {
                int v = e[i].to;
    
                if (!e[i].val || dep[v])
                    continue;
    
                q.push(v), dep[v] = dep[u] + 1, now[v] = h[v];
    
                if (v == t)
                    return true;
            }
        }
    
        return false;
    }
    int DFS(int u, int sum) 
    {
        if (u == t)
            return sum;
    
        int res = 0;
    
        for (int &i = now[u]; i && sum; i = e[i].nxt) 
        {
            int v = e[i].to;
    
            if (dep[v] != dep[u] + 1 || !e[i].val)
                continue;
    
            int k = DFS(v, min(sum, e[i].val));
            e[i].val -= k, e[i ^ 1].val += k;
            ans[i >> 1] += ((i & 1) ? -1 : 1) * k;
            sum -= k, res += k;
        }
    
        return res;
    }
    bool dinic() 
    {
        bool flag = true;
    
        while (BFS())
            DFS(s, INF);
    
        for (int i = (m << 1) + 2; i <= idx; i += 2)
            flag &= !e[i].val;
    
        return flag;
    }
    
    int main() 
    {
        scanf("%d%d", &n, &m), t = n + 1;
    
        for (int i = 1, u, v, l, r; i <= m; i++)
            scanf("%d%d%d%d", &u, &v, &l, &r), w[u] -= l, w[v] += l, ans[i] = l, addEdge(u, v, r - l), addEdge(v, u, 0);
    
        for (int i = 1; i <= n; i++)
            if (w[i] > 0)
                addEdge(s, i, w[i]), addEdge(i, s, 0);
            else if (w[i] < 0)
                addEdge(i, t, -w[i]), addEdge(t, i, 0);
    
        if (!dinic())
            return puts("NO") & 0;
    
        puts("YES");
    
        for (int i = 1; i <= m; i++)
            printf("%d\n", ans[i]);
    
        return puts("") & 0;
    }
    
    

    信息

    ID
    5546
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者