http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1328. 航班安排(王钦石)
时间限制:1.0s   内存限制:256.0MB  
总提交次数:255   AC次数:79   平均分:35.04
将本题分享到:
   
 
背景
  1.wqs爱好模拟飞行。
  2.clj开了一家神犇航空,由于clj还要玩游戏,所以公司的事务由你来打理。
  注意:题目中只是用了这样一个背景,并不与真实/模拟飞行相符
问题描述
  神犇航空有K架飞机,为了简化问题,我们认为每架飞机都是相同的。神犇航空的世界中有N个机场,以0..N-1编号,其中0号为基地机场,每天0时刻起飞机才可以从该机场起飞,并不晚于T时刻回到该机场。一天,神犇航空接到了M个包机请求,每个请求为在s时刻从a机场起飞,在恰好t时刻到达b机场,可以净获利c。设计一种方案,使得总收益最大。
输入格式
  第一行,4个正整数N,M,K,T,如题目描述中所述;
  以下N行,每行N个整数,描述一个N*N的矩阵t,t­i,j表示从机场i空载飞至机场j,需要时间ti,j
  以下N行, 每行N个整数,描述一个N*N的矩阵f,f­i,j表示从机场i空载飞至机场j,需要费用fi,j
  以下M行,每行5个整数描述一个请求,依次为a,b,s,t,c。
输出格式
  仅一行,一个整数,表示最大收益。
样例输入
2 1 1 10
0 5
5 0
0 5
5 0
0 1 0 5 10
样例输出
5
数据规模及约定
  对于10%的测试数据,K=1;
  另有20%的测试数据,K=2;
  对于全部的测试数据,N,M<=200,K<=10,T<=3000,ti,j<=200,fi,j<=2000,0<=a,b<N,0<=s<=t<=T,0<=c<=10000,ti,i=fi,i=0,ti,j<=ti,k+tk,j,fi,j<=fi,k+fk,j