#1185531 (C++17) No.3699 引き抜き交渉

• 問題: No.3699 引き抜き交渉
• ユーザー: GOTKAKO
• 提出日時: 2026-09-10 00:20:26
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 3,495 bytes
• コンパイル時間: 1,621 ms
• コンパイル使用メモリ: 225,396 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-10 00:20:32
• 合計ジャッジ時間: 3,016 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 15

ソースコード

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

struct edge{ int to; long long cap; int rev;};
class Dinic{
    public:
    int n;
    vector<pair<int,int>> Es; //i番目の辺がどこにあるか.
    vector<vector<edge>> Graph;
 
    Dinic():n(0){}
    Dinic(int N):n(N),Graph(N){}
 
    int addedge(int u, int v, long long c){ //u->vに容量c.
        int m = Es.size();
        Es.push_back({u,Graph.at(u).size()});
        int gv = Graph.at(v).size(), gu = Graph.at(u).size();
        Graph.at(u).push_back(edge{v,c,gv});
        Graph.at(v).push_back(edge{u,0,gu});
        return m;
    }
 
    long long maxflow(int s, int t,long long limit = numeric_limits<long long>::max()){ //s->tにいくつ流せるか.
        long long ret = 0;
        vector<int> dist(n),search(n);
        auto bfs = [&]() -> void {
            queue<int> Q;
            fill(dist.begin(),dist.end(),-1);
            dist.at(s) = 0,Q.push(s);
            while(Q.size()){
                int pos = Q.front(); Q.pop();
                for(auto e : Graph.at(pos)){
                    if(e.cap == 0 || dist.at(e.to) != -1) continue;
                    dist.at(e.to) = dist.at(pos)+1;
                    if(e.to == t) return;
                    Q.push(e.to);
                }
            }
        };
        auto dfs = [&](auto dfs,int pos,long long f){
            if(pos == s) return f;
            long long flow = 0;
            int nowd = dist.at(pos);
            for(int &i=search.at(pos); i<Graph.at(pos).size(); i++){
                edge &e = Graph.at(pos).at(i);
                if(nowd <= dist.at(e.to) || Graph.at(e.to).at(e.rev).cap == 0) continue;
                long long now = dfs(dfs,e.to,min(f-flow,Graph.at(e.to).at(e.rev).cap));
                if(now <= 0) continue;
                Graph.at(pos).at(i).cap += now;
                Graph.at(e.to).at(e.rev).cap -= now;
                flow += now;
                if(flow == f) break;
            }
            return flow;
        };
 
        while(ret < limit){
            bfs();
            if(dist.at(t) == -1) break;
            fill(search.begin(),search.end(),0);
            while(ret < limit){
                long long f = dfs(dfs,t,limit-ret);
                if(f == 0) break;
                ret += f;
            }
        }
        return ret;
    }
 
    vector<pair<int,int>> mincost(int s){ //maxflowの後の復元
        vector<bool> already(n);
        queue<int> Q;
        Q.push(s),already.at(s) = true;
        while(Q.size()){
            int pos = Q.front(); Q.pop();
            for(auto e : Graph.at(pos)) if(e.cap && !already.at(e.to)) already.at(e.to) = true,Q.push(e.to);
        }
 
        vector<pair<int,int>> ret;
        for(auto [pos,i] : Es) if(already.at(pos)){
            edge &e = Graph.at(pos).at(i);
            if(!already.at(e.to)) ret.push_back({pos,e.to});
        }
        return ret; //[from,to]は辺の追加順になっている.
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M; cin >> N >> M;
    int s = N,t = s+1;
    Dinic Z(N+2);   
    long long answer = 0;
    for(int i=0; i<N; i++){
        int a,b; cin >> a >> b;
        answer += max(a,b);
        if(a == b) continue;
        if(a > b) Z.addedge(s,i,a-b);
        if(a < b) Z.addedge(i,t,b-a);
    }
    while(M--){
        int a,b,c; cin >> a >> b >> c,a--,b--;
        Z.addedge(a,b,c);
        Z.addedge(b,a,c);
    }
    cout << answer-Z.maxflow(s,t) << endl;
}