結果

問題 No.654 Air E869120
ユーザー 沙耶花沙耶花
提出日時 2020-05-07 15:33:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,744 bytes
コンパイル時間 2,844 ms
コンパイル使用メモリ 234,764 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-16 07:53:36
合計ジャッジ時間 5,423 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000

template <typename T>
struct Dinic{
	struct edge{
		int to;
		T weight;
		int ind;
	};
	vector<vector<edge>> E;
	T inf;
	
	Dinic(vector<vector<pair<int,T>>> &e,T iv = 1000000001){
		inf = iv;
		E.resize(e.size(),vector<edge>());
		for(int i=0;i<e.size();i++){
			for(int j=0;j<e[i].size();j++){
				edge t = {e[i][j].first,e[i][j].second,0};
				E[i].push_back(t);
			}
		}
		for(int i=0;i<e.size();i++){
			for(int j=0;j<e[i].size();j++){
				E[i][j].ind = E[E[i][j].to].size();
				edge t = {i,0,j};
				E[E[i][j].to].push_back(t);
			}
		}
	}
	
	T maximum_flow(int s,int t){
		
		T ret = 0;
		
		while(true){
			vector<int> dis(E.size(),-1);
			queue<int> Q;
			Q.push(s);
			dis[s] = 0;
			while(Q.size()!=0){
				int u = Q.front();
				Q.pop();
				for(int i=0;i<E[u].size();i++){
					if(E[u][i].weight<=0)continue;
					int v = E[u][i].to;
					if(dis[v]!=-1)continue;
					dis[v] = dis[u]+1;
					Q.push(v);
				}
			}
			if(dis[t]==-1)break;
			
			vector<int> it(E.size(),0);
			
			while(true){
				T F = dfs(s,t,inf,it,dis);
				if(F==0)break;
				ret+=F;
			}
		}
		return ret;
	}
	
	T dfs(int now,int t,T f,vector<int> &it,vector<int> &dis){
		if(now==t)return f;
		
		for(int &i=it[now];i<E[now].size();i++){
			int to = E[now][i].to;
			T weight = E[now][i].weight;
			if(weight<=0||dis[now]+1!=dis[to]){
				continue;
			}
			T F = dfs(to,t,min(f,weight),it,dis);
			if(F!=0){
				E[now][i].weight-=F;
				E[E[now][i].to][E[now][i].ind].weight+=F;
				return F;
			}
		}
		return 0;
	}
	
};

int main(){

	int N,M;
	cin>>N>>M;
	long long d;
	cin>>d;
	
	vector<vector<vector<long long>>> E(N,vector<vector<long long>>());
	
	for(int i=0;i<M;i++){
		long long u,v,p,q,w;
		cin>>u>>v>>p>>q>>w;
		u--;v--;
		E[u].push_back({p,q,v,w});
	}
	
	vector<int> num(N,0);
	for(int i=1;i<N;i++){
		num[i] = num[i-1] + E[i-1].size();
	}
	
	vector<vector<pair<int,long long>>> E2(M+2,vector<pair<int,long long>>());
	
	for(int i=0;i<N;i++){
		sort(E[i].begin(),E[i].end());
		for(int j=0;j<E[i].size();j++){
			if(j+1!=E[i].size())E2[num[i]+j].emplace_back(num[i]+j+1,Inf);
		}
	}
	
	for(int i=0;i<N;i++){
		for(int j=0;j<E[i].size();j++){
			long long q = E[i][j][1];
			long long to = E[i][j][2];
			long long w = E[i][j][3];
			if(to==N-1){
				E2[num[i]+j].emplace_back(M+1,w);
				continue;
			}
			for(int k=0;k<E[to].size();k++){
				if(q+d<=E[to][k][0]){
					E2[num[i]+j].emplace_back(num[to]+k,w);
					break;
				}
			}
		}
	}
		
	for(int i=0;i<E[0].size();i++){
		E2[M].emplace_back(i,Inf);
	}
	
	Dinic<long long> D(E2,Inf);
	cout<<D.maximum_flow(M,M+1)<<endl;
	
	return 0;
}
0