結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー なお
提出日時 2015-01-07 00:13:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,328 bytes
コンパイル時間 1,782 ms
コンパイル使用メモリ 172,176 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 10:45:02
合計ジャッジ時間 2,575 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define pb                  push_back
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
const int MOD = (int)(1e9+7);

#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)

class MaxFlow {
    static const int INF = 1<<29;
public:
    VVI C, E, F;
    MaxFlow(int n) : C(n, VI(n)), E(n), F(n, VI(n)){;}
    void add(int u, int v, int c){ C[u][v] += c; E[u].pb(v); E[v].pb(u); }
    int aug(const int u, const int t, const VI &P, VI &fin, int cur){
        if (u == t || cur == 0) return cur;
        if (fin[u]) return 0;
        fin[u] = true;
        int m = 0;
        FOREACH(it, E[u]){
            const int &v = *it;
            if(P[v] <= P[u]) continue;
            m = aug(v, t, P, fin, min(cur, C[u][v] - F[u][v]));
            if(m > 0){
                F[u][v] += m; F[v][u] -= m;
                fin[u] = false;
                break;
            }
        }
        return m;
    }
    int solve(const int s, const int t){
        int n = C.size(), maxflow = 0; VI P(n), M(n);
        while(1){
            P = VI(n,-1); P[s] = 0; queue<int> q; q.push(s);
            for(int d = n; !q.empty() && P[q.front()] < d; ){
                int u = q.front(); q.pop();
                if(u == t) d = P[u];
                FOREACH(it, E[u]){
                    const int &v = *it;
                    if(P[v] >= 0 || C[u][v] - F[u][v] <= 0) continue;
                    P[v] = P[u]+1; q.push(v);
                }
            }
            VI fin(n); bool cont = false;
            while(1){
                int m = aug(s, t, P, fin, INF);
                if(m == 0) break;
                maxflow += m; cont = true;
            }
            if(!cont) break;
        }
        return maxflow;
    }
};

int B[44],C[44];
const int INF = 1<<28;
int main(){
    int N,M;
    cin >> N;
    MaxFlow mf(202);

    int sum = 0;
    REP(i,N){
        int b,c; cin >> b >> c;
        mf.add(200,i,b);
        mf.add(i,100+i,INF);
        mf.add(100+i,201,c);
        sum += b+c;
    }
    cin >> M;
    REP(i,M){
        int d,e; cin >> d >> e;
        mf.add(d,100+e,INF);
    }
    cout << sum - mf.solve(200,201) << endl;
}
0