记录编号	137836	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]航班安排	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.257 s
提交时间	2014-11-05 11:41:20	内存使用	0.63 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int SIZEn=210,SIZEN=410,INF=0x7fffffff/2;
int N,S,T;//0~N
int ansflow=0,anscost=0,mxflow;
class EDGE{
public:
	int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
void addedge(int from,int to,int cap,int cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,-cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int dis[SIZEN];
int father[SIZEN];
bool inq[SIZEN];
queue<int> Q;
bool SPFA(int S,int T){//最大费用最大流
	if(ansflow==mxflow) return false;
	for(int i=0;i<=N;i++) dis[i]=-INF;
	memset(inq,0,sizeof(inq));
	while(!Q.empty()) Q.pop();
	dis[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			EDGE &e=edges[c[x][i]];
			if(e.cap<=e.flow) continue;
			if(dis[x]+e.cost>dis[e.to]){
				dis[e.to]=dis[x]+e.cost;
				father[e.to]=c[x][i];
				if(!inq[e.to]){
					inq[e.to]=true;
					Q.push(e.to);
				}
			}
		}
	}
	if(dis[T]==INF) return false;
	int flow=INF,x;
	x=T;
	while(x!=S){
		EDGE &e=edges[father[x]];
		flow=min(flow,e.cap-e.flow);
		x=e.from;
	}
	flow=min(flow,mxflow-ansflow);
	ansflow+=flow,anscost+=flow*dis[T];
	x=T;
	while(x!=S){
		edges[father[x]].flow+=flow;
		edges[father[x]^1].flow-=flow;
		x=edges[father[x]].from;
	}
	return true;
}
int MCMF(int S,int T,int mx){
	mxflow=mx;
	ansflow=anscost=0;
	while(SPFA(S,T));
	return anscost;
}
int n,m,K,mxtim;
int t[SIZEn][SIZEn],f[SIZEn][SIZEn];
class QUERY{
public:
	int a,b,s,t,c;
}deal[SIZEn];
void makegraph(void){
	N=2*m+1;
	S=N-1,T=N;
	for(int i=0;i<m;i++) addedge(i*2,i*2+1,1,deal[i].c);
	for(int i=0;i<m;i++){
		if(t[0][deal[i].a]<=deal[i].s) addedge(S,i*2,1,-f[0][deal[i].a]);
		if(t[deal[i].b][0]<=mxtim-deal[i].t) addedge(i*2+1,T,1,-f[deal[i].b][0]);
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j) continue;
			if(t[deal[i].b][deal[j].a]<=deal[j].s-deal[i].t)
				addedge(i*2+1,j*2,1,-f[deal[i].b][deal[j].a]);
		}
	}
}
void read(void){
	scanf("%d%d%d%d",&n,&m,&K,&mxtim);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&t[i][j]);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&f[i][j]);
	for(int i=0;i<m;i++) scanf("%d%d%d%d%d",&deal[i].a,&deal[i].b,&deal[i].s,&deal[i].t,&deal[i].c);
}
int main(){
	freopen("nt2012_flight.in","r",stdin);
	freopen("nt2012_flight.out","w",stdout);
	read();
	makegraph();
	printf("%d\n",MCMF(S,T,K));
	return 0;
}