游客 注册 | 登录
中文 | En

1946 - 航班安排

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

神犇航空有K架飞机，为了简化问题，我们认为每架飞机都是相同的。神犇航空的世界中有N个机场，以0..N-1编号，其中0号为基地机场，每天0时刻起飞机才可以从该机场起飞，并不晚于T时刻回到该机场。一天，神犇航空接到了M个包机请求，每个请求为在s时刻从a机场起飞，在恰好t时刻到达b机场，可以净获利c。设计一种方案，使得总收益最大。

题目输入

 第一行，4个正整数N,M,K,T，如题目描述中所述；

　　以下N行，每行N个整数，描述一个NN的矩阵t，t­i,j表示从机场i空载飞至机场j，需要时间ti,j；
　　以下N行, 每行N个整数，描述一个NN的矩阵f，f­i,j表示从机场i空载飞至机场j，需要费用fi,j；
　　以下M行，每行5个整数描述一个请求，依次为a,b,s,t,c。

对于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。

题目输出

 仅一行，一个整数，表示最大收益。

输入/输出样例

输入格式

2 1 1 10
0 5
5 0
0 5
5 0
0 1 0 5 10

输出格式

5

C++解答

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
#define time TTTT
using namespace std;
int n,m,k,tim,t[205][205],w[205][205],head[100005],vis[100005],dis[100005],cnt=1,cost,ans,time,st,ed;
struct node
{
    int a,b,s,t,c;
}q[1005];struct Edge{int v,nx,s,val;}e[1000005];
inline int read(){int ret=0,ff=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}return ret*ff;}inline void add(int x,int y,int val,int s){
    e[++cnt].v=y;e[cnt].val=val;e[cnt].s=s;e[cnt].nx=head[x];head[x]=cnt;
}
inline bool spfa()
{
    for(int i=0;i<=ed;i++)dis[i]=-1e9,vis[i]=0;queue<int>q;dis[st]=0;q.push(st);while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=head[now];i;i=e[i].nx){int v=e[i].v;if(dis[v]<dis[now]+e[i].val&&e[i].s){dis[v]=dis[now]+e[i].val;if(!vis[v]){vis[v]=1;q.push(v);}}}}return dis[ed]!=-1e9;
}
int dfs(int now,int ma){
    if(now==ed){ans+=ma;return ma;}vis[now]=time;int used=0,t;for(int i=head[now];i;i=e[i].nx){int v=e[i].v;if((vis[v]!=time||v==ed)&&e[i].s&&dis[v]==dis[now]+e[i].val){if(t=dfs(v,min(ma-used,e[i].s))){e[i].s-=t;e[i^1].s+=t;cost+=t*e[i].val;used+=t;if(used==ma) break;}}}return used;
}
signed main(){n=read(),m=read(),k=read(),tim=read();for(int i=0;i<n;i++)for(int j=0;j<n;j++)t[i][j]=read();for(int i=0;i<n;i++)for(int j=0;j<n;j++)w[i][j]=read();st=m*2+5,ed=m*2+10;for(int i=1;i<=m;i++){q[i].a=read();q[i].b=read();q[i].s=read();q[i].t=read();q[i].c=read();}for(int i=1;i<=m;i++){add(i*2-1,i*2,q[i].c,1);add(i*2,i*2-1,-q[i].c,0);if(q[i].t+t[q[i].b][0]<=tim){add(i*2,ed,-w[q[i].b][0],1e9);add(ed,i*2,w[q[i].b][0],0);}else continue;if(t[0][q[i].a]<=q[i].s){add(st+1,i*2-1,-w[0][q[i].a],1e9);add(i*2-1,st+1,w[0][q[i].a],0);}for(int j=1;j<=m;j++){if(q[i].t+t[q[i].b][q[j].a]<=q[j].s){
                add(i*2,j*2-1,-w[q[i].b][q[j].a],1e9);
                add(j*2-1,i*2,w[q[i].b][q[j].a],0);
            }
        }
    }
    add(st,st+1,0,k);
    add(st+1,st,0,0);
    while(spfa()){
        do{
            time++;
            dfs(st,1e9);
        }while(vis[ed]==time);
    }
    printf("%d",cost);
    return 0;
}
请先登陆