https://www.luogu.org/problemnew/show/P4452

又一道看题解的费用流。

注意时间也影响节点，像题解那样建边就少很多了。

#include
     
      using namespace std;const int MAXN=700005+1;const int MAXM=700000;const int INF=0x3f3f3f3f;struct Edge{    int to,next,cap,flow,cost;}edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int n;void init(){    tol=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int cap,int cost){    edge[tol].to=v;    edge[tol].cap=cap;    edge[tol].cost=cost;    edge[tol].flow=0;    edge[tol].next=head[u];    head[u]=tol++;    edge[tol].to=u;    edge[tol].cap=0;    edge[tol].cost=-cost;    edge[tol].flow=0;    edge[tol].next=head[v];    head[v]=tol++;}bool spfa(int s,int t){    queue
      
        q;    memset(dis,INF,sizeof(dis));    memset(vis,false,sizeof(vis));    memset(pre,-1,sizeof(pre));    dis[s]=0;    vis[s]=true;    q.push(s);    while(!q.empty()){        int u=q.front();        q.pop();        vis[u]=false;        for(int i=head[u];i!=-1;i=edge[i].next){            int v=edge[i].to;            if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){                dis[v]=dis[u]+edge[i].cost;                pre[v]=i;                if(!vis[v]){                    vis[v]=true;                    q.push(v);                }            }        }    }    if(pre[t]==-1)        return false;    else        return true;}int minCostMaxFlow(int s,int t,int &cost){    int flow=0;    cost=0;    while(spfa(s,t)){        int Min=INF;        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){            if(Min>edge[i].cap-edge[i].flow)                Min=edge[i].cap-edge[i].flow;        }        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){            edge[i].flow+=Min;            edge[i^1].flow-=Min;            cost+=edge[i].cost*Min;        }        flow+=Min;    }    return flow;}/*int main(){    int M,S,T;    scanf("%d%d%d%d",&N,&M,&S,&T);    init(N);    while(M--){        int u,v,cap,cost;        scanf("%d%d%d%d",&u,&v,&cap,&cost);        addedge(u,v,cap,cost);    }    int cost=0;    int flow=minCostMaxFlow(S,T,cost);    printf("%d %d\n",flow,cost);}*/int getid(int id,int T){    return T*200+id;}int g[205][205]={};int co[205][205]={};struct Node{    int a,b,s,t,c;}node[2000];int main() {    init();    int s=0,s1=700005,T,m,k;    scanf("%d%d%d%d",&n,&m,&k,&T);    int t=getid(0,T);    addedge(s1,s,k,0);//不超过k架飞机    for(int i=0;i
       
        =0)                addedge(getid(i,t1-ti),u,1,co[i][a]);        }       // cout<<"cost="<
        
         <