結果

問題 No.654 Air E869120
ユーザー daikiti10915465daikiti10915465
提出日時 2020-05-21 19:14:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,750 bytes
コンパイル時間 1,839 ms
コンパイル使用メモリ 170,816 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-09 23:28:02
合計ジャッジ時間 3,215 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
6,940 KB
testcase_02 WA -
testcase_03 AC 2 ms
6,944 KB
testcase_04 WA -
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 WA -
testcase_08 AC 2 ms
6,944 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 AC 3 ms
6,940 KB
testcase_30 AC 4 ms
6,940 KB
testcase_31 AC 4 ms
6,940 KB
testcase_32 AC 3 ms
6,944 KB
testcase_33 AC 3 ms
6,940 KB
testcase_34 AC 4 ms
6,940 KB
testcase_35 AC 1 ms
6,940 KB
testcase_36 AC 2 ms
6,940 KB
testcase_37 AC 2 ms
6,944 KB
testcase_38 AC 2 ms
6,940 KB
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;
ll const mod=998244353;
const ll MAX=1010;
using vi=vector<int>;
using vc=vector<char>;
using vs=vector<string>;
using vvi =vector<vector<int>>;
using vvc=vector<vector<char>>;
using vvp =vector<vector<P>>;
int d;
struct edge{
    int to,cap,rev,st,et;
    edge(int t,int c,int r,int s,int e)
    : to(t),cap(c),rev(r),st(s),et(e){}
};

struct graf{
    vector<edge> G[MAX];
    int used[MAX];

    void init(){memset(used,0,sizeof(used));}
    void add(int from,int to,int cap,int st,int et){
        G[from].push_back(edge(to,cap,(int)G[to].size(),st,et));
        G[to].push_back(edge(from,0,(int)G[from].size()-1,INF,st));
    }

    int dfs(int s, int t, int f, int time){
        if(s==t)return f;
        used[s]=1;
        for(edge& e:G[s]){
            if(used[e.to]==1||e.cap<=0||time>0&&time+d>e.st)continue;
            int x=dfs(e.to,t,min(f,e.cap),e.et);
            if(x<=0)continue;
            e.cap-=x;
            G[e.to][e.rev].cap+=x;
            return x;
        }
        return 0;
    }

    int max_flow(int s,int t){
        int ans=0;
        while(1){
            init();
            int f=dfs(s,t,INF,0);
            if(f==0)return ans;
            ans+=f;
        }
    }
    
};

int main(){
    int n,m;
    cin>>n>>m>>d;
    graf mf;
    rep(i,m){
        int u,v,p,q,w;
        cin>>u>>v>>p>>q>>w;
        u--,v--;
        mf.add(u,v,w,p,q);
    }
    cout<<mf.max_flow(0,n-1)<<endl;
    return 0;
}
0