結果

問題 No.654 Air E869120
ユーザー eQeeQe
提出日時 2019-02-24 13:35:00
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,037 bytes
コンパイル時間 1,641 ms
コンパイル使用メモリ 75,956 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-08-23 12:46:48
合計ジャッジ時間 3,140 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
4,376 KB
testcase_02 WA -
testcase_03 AC 1 ms
4,376 KB
testcase_04 WA -
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 WA -
testcase_08 AC 2 ms
4,376 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 AC 2 ms
4,376 KB
testcase_36 WA -
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 1 ms
4,376 KB
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define pb(t) push_back(t)
#define ft first
#define sc second
#define pt(num) cout << num << "\n"
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

class Edge {
public:
    ll t, cap, rev, dep, arr;
    Edge(ll t, ll cap, ll rev, ll dep, ll arr):
    t(t), cap(cap), rev(rev), dep(dep), arr(arr) {}
};

ll N;
vector<Edge> g[111];
ll used[111];

ll dfs(ll v, ll goal, ll f, ll time) {
    if(v==goal) return f;
    used[v]=1;
    ll i;
    for(i=0; i<g[v].size(); i++) {
        Edge &e=g[v][i];
        if(time>e.dep) continue;
        if(!used[e.t] && e.cap>0) {
            ll d=dfs(e.t, goal, min(f, e.cap), time+e.arr);
            if(d>0) {
                e.cap-=d;
                g[e.t][e.rev].cap+=d;
                return d;
            }
        }
    }
    
    return 0;   //goalまでのパスが見つからなかったとき
}

ll maxFlow(ll s, ll t) {
    ll flow=0;
    while(1) {
        memset(used, 0, sizeof(used));
        
        ll f=dfs(s, t, INF, 0);
        if(f==0) return flow;
        flow+=f;
    }
}

void addEdge(ll from, ll to, ll dep, ll arr, ll cap) {
    g[from].pb(Edge(to, cap, g[to].size(), dep, arr));
    g[to].pb(Edge(from, 0, g[from].size()-1, dep, arr));
}

int main(void) {
    ll M, d;
    cin >> N >> M >> d;
    ll i;
    
    for(i=0; i<M; i++) {
        ll u, v, p, q, w;
        cin >> u >> v >> p >> q >> w;
        u--; v--;
        addEdge(u, v, p, q+d, w);
    }
    
    pt(maxFlow(0, N-1));
    
}
0