結果

問題 No.654 Air E869120
ユーザー SJiro64SJiro64
提出日時 2019-01-08 11:33:19
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 5,117 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 80,128 KB
実行使用メモリ 58,576 KB
最終ジャッジ日時 2024-05-03 03:40:24
合計ジャッジ時間 13,554 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 155 ms
41,600 KB
testcase_01 AC 150 ms
41,604 KB
testcase_02 AC 151 ms
41,492 KB
testcase_03 AC 150 ms
41,688 KB
testcase_04 AC 151 ms
41,736 KB
testcase_05 AC 148 ms
41,344 KB
testcase_06 AC 150 ms
41,544 KB
testcase_07 AC 149 ms
41,464 KB
testcase_08 AC 154 ms
41,612 KB
testcase_09 AC 149 ms
41,320 KB
testcase_10 AC 344 ms
47,448 KB
testcase_11 AC 301 ms
46,876 KB
testcase_12 AC 319 ms
47,088 KB
testcase_13 AC 316 ms
47,064 KB
testcase_14 AC 306 ms
46,692 KB
testcase_15 AC 312 ms
47,232 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 265 ms
46,552 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 248 ms
46,344 KB
testcase_26 WA -
testcase_27 AC 266 ms
46,088 KB
testcase_28 WA -
testcase_29 AC 260 ms
46,224 KB
testcase_30 AC 271 ms
46,816 KB
testcase_31 AC 265 ms
45,792 KB
testcase_32 AC 268 ms
46,620 KB
testcase_33 AC 267 ms
45,896 KB
testcase_34 AC 266 ms
46,904 KB
testcase_35 AC 136 ms
41,080 KB
testcase_36 AC 140 ms
41,596 KB
testcase_37 AC 140 ms
41,320 KB
testcase_38 AC 131 ms
41,236 KB
testcase_39 AC 152 ms
41,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
public class Main {
	static final int INF=Integer.MAX_VALUE;
	static boolean[] used;
	static int flow;
	
	static int V;//頂点
	static int E;//辺
	
	static List<List<edge>> G;//listの二重構造で隣接リスト実現

	static int N;
	static int M;//飛行機の便の数
	static int d;
	
	static int[]u;//uから
	static int[]v;//Vまで飛ぶ。
	static int[]p;//時刻pに離陸
	static int[]q;//時刻qに到着
	static int[]w;//飛行機に乗れる人数
	
	static List<List<Integer>>dic;
	static List<List<Integer>>dic2;
	
	static int[]sz;
	
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc= new Scanner(System.in);
		
		N= sc.nextInt();
		M= sc.nextInt();
		d= sc.nextInt();
		
		u= new int[M];
		v= new int[M];
		p= new int[M];
		q= new int[M];
		w= new int[M];
		
		
		//dic 作成
		dic= new ArrayList<>();
		for(int i=0;i<N;i++)	dic.add(new ArrayList<>());
		
		for(int i=0;i<M;i++){
			u[i]= sc.nextInt();
			v[i]= sc.nextInt();
			p[i]= sc.nextInt();
			q[i]= sc.nextInt();
			w[i]= sc.nextInt();
			
			//街を0オリジンで格納したい
			u[i]--;
			v[i]--;
			
			//Q+dに到着とすることで、乗り換えの時差を解決
			q[i]+= d;
			
			dic.get(u[i]).add(p[i]);
			dic.get(v[i]).add(q[i]);
		}
		
		sc.close();
		
		
		//dicをhashsetを使って座圧
		//dic2= new ArrayList<>(new LinkedHashSet<>(dic));これだとダメ、多分dic.get(i)[街]のところが座圧される　
		dic2= new ArrayList<>();
		
		for(int i=0;i<N;i++){
			List<Integer> hash= new ArrayList<>(new LinkedHashSet<>(dic.get(i)));
			Collections.sort(hash);
			dic2.add(hash);
		}
		
		
		//Gの作成
		sz= new int[N];//それぞれの街の頂点の累積和を記録[個]
		sz[0]=dic2.get(0).size();
		for(int i=1;i<N;i++)sz[i]=sz[i-1]+ dic2.get(i).size();
		
		V= sz[N-1];//全ての頂点の数[個]
		
		
		//使う頂点を一列の隣接リストGに変換したい
		G= new ArrayList<>();
		for(int i=0;i<= V;i++)G.add(new ArrayList<>());//全ての頂点を一列にした
		
		for(int i=0;i<N;i++){//行を繋げる
			int start=0;
			if(i > 0)start += sz[i-1];
			
			int n= dic2.get(i).size();//個
			
			//添字stから始まる、n個
			for(int j=0;j<n-1;j++){
				int from=start+ j;
				int to= from+ 1;
				add_edge(from,to,INF);
			}	
		}
		
		
		
		for(int i=0;i<M;i++){//移動辺を繋げる(G[u[i]][p[i]]→G[v[i]][q[i]])
			//G[u[i]][p[i]]の添字を探す
			
			//G.get(u[i])の位置
			int startU= 0;
			if(u[i]>0)startU= sz[u[i]-1];
			
			int u_p= lower_bound(dic2.get(u[i]),p[i]);//p[i]は街u[i]の中で何番目の頂点か
			
			int from= startU+ u_p;
			
			
			//G.get(v[i])の位置
			int startV=0;
			if(v[i]>0)startV= sz[v[i]-1];
			
			int v_q= lower_bound(dic2.get(v[i]),q[i]);//q[i]は街v[i]の中で何番目の頂点か
			
			int to= startV+ v_q;
			
			
			add_edge(from,to,w[i]);
		}
	
		//max_flow
		int ans= max_flow(0,V-1);//sz[]はそれぞれの街の頂点の"個数"の累積和だから、0origenでは-1
		System.out.println(ans);

	}
	
	static void add_edge(int from,int to,int cap){
		G.get(from).add(new edge(to,cap,G.get(to).size()));
		//同時に逆辺も辿れるようにするため、に双方向に紐をつける。
		G.get(to).add(new edge(from,0,G.get(from).size()-1));
	}
	
	static int lower_bound(List<Integer>A,int key){
		//binary_searchで実装。keyが街Aの何個目の要素か、indexを返す
				int left= 0;
				int right= A.size();
				int mid;
				
				while(left< right){
					mid= (left+ right)/2;
					if(A.get(mid) == key)return mid;

					if(key< A.get(mid))right= mid;
					if(A.get(mid)< key)left= mid+1;
				}
				
				return 0;//返せないことはあり得ないが、便宜上
	}


static int dfs(int v,int t,int f){
	if(v == t)return f;//tまでたどり着いた
	
	used[v] = true;
	
	for(int i=0;i<G.get(v).size();i++){
		edge e =G.get(v).get(i);
		
		if(used[e.to] != true && e.cap >0){
			int d= dfs(e.to,t,Math.min(f, e.cap));
			//min(f,e.cap)はまだ流す量を決めている段階。暫定の流量
			
			if(d>0){//tまでたどり着いた(流せる)時
			//v==tのreturn fを受けて、ここで初めてf(=d)を流す
				e.cap -=d;
				G.get(e.to).get(e.rev).cap += d;//直接逆辺のcを変化させて、
				return d;//各辺でdを流すために戻る。　
			}	
		}	
	}
		return 0;
		/* 
		 * tまでたどり着けなかった（途中の辺の容量が0だったのでdfs(e.to,cap,min(f,e.cap))でd=0が返ってくる）
		 * 最初f==INFだから、d==0(f==0)の時は、全ての辺を辿ってみたけど全く流せなかったってこと
		 * d>0に引っかからなかったとも言える
		 */
}
	

static int max_flow(int s,int t) {
	int flow= 0;
	
	while(true){
		used =new boolean[V];
		
		int f= dfs(s,t,INF);
		if(f == 0)return flow;//if(もうこれ以上流せない)return
		flow +=f;
	}
	
}

static class edge {
	int to;
	int cap;
	int rev;//逆辺にアクセスする
	
	edge(int to,int cap,int rev){
		this.to =to;
		this.cap =cap;
		this.rev =rev;
	}

}

}
0