[国家集训队]航班安排

╰半夏微凉° 2021-12-13 03:07 179阅读 0赞

题目链接：[点这里][Link 1]

## Solution： ##

本题首先把每个请求拆点，然后我们只需要判断时间限制，再来连边就行了

注意给出的\\(f,t\\)两个矩阵都是在空载情况下的定义

## Code： ##

#include<bits/stdc++.h>
    #define inf 1926081700
    using namespace std;
    const int N=211;
    int n,m,k,edt,cnt=1,S,T;
    int head[N<<1],f[N][N],t[N][N];
    struct Edge{int nxt,to,v,w;}edge[N*N<<1];
    struct airline{int st,ed,t0,t1,c;}p[N];
    void ins(int x,int y,int v,int w){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;edge[cnt].v=v;
        edge[cnt].w=w;head[x]=cnt;
    }
    namespace Network_Flow{
        queue<int> q;
        int delta,maxcost;
        int vis[N<<1],dis[N<<1],pre[N<<1];
        int spfa(){
            pre[T]=0,delta=inf;
            memset(vis,0,sizeof(vis));
            memset(dis,0x3f,sizeof(dis));
            q.push(S),dis[S]=0,vis[S]=1;    
            while(!q.empty()){
                int x=q.front();q.pop();vis[x]=0;
                for(int i=head[x];i;i=edge[i].nxt){
                    int y=edge[i].to;
                    if(edge[i].v&&dis[x]+edge[i].w<dis[y]){
                        dis[y]=dis[x]+edge[i].w;
                        delta=min(delta,edge[i].v);
                        pre[y]=i;if(!vis[y]) vis[y]=1,q.push(y);
                    }
                }
            }return pre[T];
        }
        void update(){
            int x=T;
            while(x!=S){
                int i=pre[x];
                edge[i].v-=delta;
                edge[i^1].v+=delta;
                x=edge[i^1].to;
            }maxcost+=delta*dis[T];
        }
        void Edmond_Karp(){
            while(spfa()) update();
            printf("%d\n",-maxcost);
        }
    }
    int read(){
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }
    int main(){
        n=read(),m=read(),k=read(),edt=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++)
                f[i][j]=read();
        for(int i=1;i<=m;i++)
            p[i].st=read(),p[i].ed=read(),p[i].t0=read(),p[i].t1=read(),p[i].c=read();
        S=(m<<1)+2,T=S+3;
        for(int i=1;i<=m;i++){
            ins((i<<1)-1,i<<1,1,-p[i].c);
            ins(i<<1,(i<<1)-1,0,p[i].c);
            if(p[i].t1+t[p[i].ed][0]<=edt){
                ins(i<<1,T,inf,f[p[i].ed][0]);
                ins(T,i<<1,0,-f[p[i].ed][0]);
            }else continue;
            if(t[0][p[i].st]<=p[i].t0){
                ins(S+1,(i<<1)-1,inf,f[0][p[i].st]);
                ins((i<<1)-1,S+1,0,-f[0][p[i].st]);
            }
            for(int j=1;j<=m;j++)
                if(p[i].t1+t[p[i].ed][p[j].st]<=p[j].t0){
                    ins(i<<1,(j<<1)-1,inf,f[p[i].ed][p[j].st]);
                    ins((j<<1)-1,i<<1,0,-f[p[i].ed][p[j].st]);
                }
        }ins(S,S+1,k,0);ins(S+1,S,0,0);
        Network_Flow::Edmond_Karp();
        return 0;
    }

转载于:https://www.cnblogs.com/NLDQY/p/10845529.html

[Link 1]: https://www.luogu.org/problemnew/show/P4452