神犇航空有K架飞机，为了简化问题，我们认为每架飞机都是相同的。神犇航空的世界中有N个机场，以0⋯N-1编号，
其中0号为基地机场，每天0时刻起飞机才可以从该机场起飞，并不晚于TT时刻回到该机场。
一天，神犇航空接到了MM个包机请求，每个请求为在ss时刻从aa机场起飞，在恰好tt时刻到达bb机场，可以净获利cc。
设计一种方案，使得总收益最大。
任务当作点，点权为1，然后拆点，连边 (1, Val [i] )
S-> begin( 1, 0) ,end-> T (1, 0)
任务之间放边( 1, - cost[ i ][ j ] )
最后再建一个 S‘' --> S ,( K, 0)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N =500, M=1e5+100;
#define inf 1e9
int all=1,hd[N],go[M],w[M],nxt[M],cost[M];
int a[N][N],tm[N][N];
int qa[N],qb[N],qs[N],qe[N],qc[N];
int TIME,K;
int S,T,n,m;
int pre[N],mn[N],dis[N],vis[N],ans=0;
void add_(int x,int y,int z,int c){
nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
w[all]=z; cost[all]=c;
swap(x,y);
nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
w[all]=0; cost[all]= -c;
}
bool spfa__max(){
int i;
queue<int> q;
q.push(S);
for(i=0;i<N;i++) dis[i]= -inf;
for(i=0;i<N;i++) vis[i]=0;
mn[S]=inf, dis[S]=0, vis[S]=1;
while(!q.empty()){
int x=q.front();
vis[x]=0;
q.pop();
for(i=hd[x];i;i=nxt[i]){
int y=go[i],z=w[i],c=cost[i];
if(w[i]==0) continue;
if(dis[x]+c>dis[y]){
dis[y]=dis[x]+c;
mn[y]=min(mn[x],z);
pre[y]=i;
if(vis[y]==0) vis[y]=1,q.push(y);
}
}
}
return dis[T]== -inf ?0:1;
}
void solve(){
int maxf=0, minc=0;
while(spfa__max()){
int x= T;
maxf+= mn[T] ,minc+= mn[T]*dis[T];
while(x!=S){
int i=pre[x];
w[i]-= mn[T];
w[i^1]+=mn[T];
x=go[i^1];
}
}
cout<< minc<<endl;
}
signed main(){
int i,j,x;
cin>>n>>m>>K>>TIME;
S=m*2+1,T=S+2;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
cin>>tm[i][j];
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
cin>>a[i][j];
add_(S,S+1,K,0);
for(int i=1;i<=m;i++)
cin>>qa[i]>>qb[i]>>qs[i]>>qe[i]>>qc[i],
qa[i]++,qb[i]++;
for(int i=1;i<=m;i++){
add_(i,i+m,1, qc[i]);
if(tm[1][qa[i]]<=qs[i])
add_(S+1,i,1, -a[1][qa[i]]);
if(qe[i]+tm[qb[i]][1]<=TIME)
add_(i+m,T,1, -a[qb[i]][1]);
for(int j=1;j<=m;j++){
if(i!=j && qe[i]+tm[qb[i]][qa[j]]<=qs[j])
add_(i+m,j,1,-a[qb[i]][qa[j]]);
}
}
solve();
}
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N =500, M=1e5+100;
#define inf 1e9
int all=1,hd[N],go[M],w[M],nxt[M],cost[M];
int a[N][N],tm[N][N];
int qa[N],qb[N],qs[N],qe[N],qc[N];
int TIME,K;
int S,T,n,m;
int pre[N],mn[N],dis[N],vis[N],ans=0;
void add_(int x,int y,int z,int c){
nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
w[all]=z; cost[all]=c;
swap(x,y);
nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
w[all]=0; cost[all]= -c;
}
bool spfa__max(){
int i;
queue<int> q;
q.push(S);
for(i=0;i<N;i++) dis[i]= -inf;
for(i=0;i<N;i++) vis[i]=0;
mn[S]=inf, dis[S]=0, vis[S]=1;
while(!q.empty()){
int x=q.front();
vis[x]=0;
q.pop();
for(i=hd[x];i;i=nxt[i]){
int y=go[i],z=w[i],c=cost[i];
if(w[i]==0) continue;
if(dis[x]+c>dis[y]){
dis[y]=dis[x]+c;
mn[y]=min(mn[x],z);
pre[y]=i;
if(vis[y]==0) vis[y]=1,q.push(y);
}
}
}
return dis[T]== -inf ?0:1;
}
void solve(){
int maxf=0, minc=0;
while(spfa__max()){
int x= T;
maxf+= mn[T] ,minc+= mn[T]*dis[T];
while(x!=S){
int i=pre[x];
w[i]-= mn[T];
w[i^1]+=mn[T];
x=go[i^1];
}
}
cout<< minc<<endl;
}
signed main(){
int i,j,x;
cin>>n>>m>>K>>TIME;
S=m*2+1,T=S+2;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
cin>>tm[i][j];
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
cin>>a[i][j];
}
add_(S,S+1,K,0);
for(int i=1;i<=m;i++)
cin>>qa[i]>>qb[i]>>qs[i]>>qe[i]>>qc[i],
qa[i]++,qb[i]++;
for(int i=1;i<=m;i++){
add_(i,i+m,1, qc[i]);
if(tm[1][qa[i]]<=qs[i])
add_(S+1,i,1, - a[1][qa[i]]);
if(qe[i]+tm[qb[i]][1]<=TIME)
add_(i+m,T,1, -a[qb[i]][1]);
for(int j=1;j<=m;j++){
if(i!=j && qe[i]+tm[qb[i]][qa[j]]<=qs[j])
add_(i+m,j,1,-a[qb[i]][qa[j]]);
}
}
solve();
}