Task Schedule

题意:有n个任务,每个任务三个参数,P,S,E,分别代表需要工作的时间,起始时间,终止时间. 工作的P天可以不连续.每天可以同时进行M个任务.问,是否有合理的安排计划.

思路:

  • 每个任务对于区间[S,E]连一条边,代表这些路径都可以尝试
  • 对于每个任务,从源点S流入P的流量
  • 对于每一天,都流向一个汇点T,容量为M

这样建好图后,跑一遍最大流,若证明一定有合理的计划

Accepted 3572 452MS 3380K 2120B G++

按理说Dinic的复杂度是. 题目中 n->1000 , m->5e5 . 但Dinic对于某些特殊的图,跑的特快

对于边容量都是1的情况,复杂度为

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e3+3,M=6e5;
const int inf=1e9+9;
int cnt;
int ver[M<<1],edge[M<<1],Next[M<<1],head[N<<1];

void add(int u,int v,int w){
    ver[++cnt]=v;edge[cnt]=w;Next[cnt]=head[u];head[u]=cnt;
}
void init(){
    memset(head,-1,sizeof head);
    cnt=1;
}
int s,t;
int dis[N];
bool bfs(){
    memset(dis,0,sizeof dis);
    dis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i!=-1;i=Next[i]){
            if(edge[i]>0 && !dis[ver[i]]){
                dis[ver[i]]=dis[x]+1;
                q.push(ver[i]);
                if(ver[i]==t)   return true;
            }
        }
    }
    return false;
}

int Dinic(int x,int flow){
    if(x==t || flow==0)    return flow;
    int res=0;
    for(int i=head[x];i!=-1;i=Next[i]){
        if( flow-res>0&&dis[ver[i]]==dis[x]+1&& edge[i]){ ///flow-res>0 少一次递归,优化
            int k=Dinic(ver[i],min(flow-res,edge[i]));
            if(!k)  dis[ver[i]]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            res+=k;
        }
    }
    return res;
}
int ks;
bool vis[600];
int main(void){
    int m,n;
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,false,sizeof vis);
        int mn=999,mx=0;
        scanf("%d%d",&n,&m);
        init();
        s=0,t=500+n+1;
        ll tot=0;
        for(int i=1;i<=n;i++){
            int p,st,ed;
            scanf("%d%d%d",&p,&st,&ed);
            tot+=p;
            add(s,500+i,p);
            add(500+i,s,0);
            for(int j=st;j<=ed;j++){
                add(500+i,j,1);
                add(j,500+i,0);
                vis[j]=true;
            }
        }
        for(int i=1;i<=500;i++){
            if(!vis[i]) continue;
            add(i,500+n+1,m);
            add(500+n+1,i,0);
        }
        ll maxflow=0;
        int flow;
        while(bfs()){
            while(flow=Dinic(s,inf)) maxflow+=flow;
        }
//        cout << maxflow <<endl;
        printf("Case %d: ",++ks);
        if(maxflow==tot)    printf("Yes\n\n");
        else    printf("No\n\n");
    }
    return 0;
}