题解：P11614 [PA 2016] 任务排序 / Szeregowanie zadań

· · 题解

P11614 [PA 2016] 任务排序 / Szeregowanie zadań 题解

简单网络流，场切了。

solution

发现这道题严格弱于P2570 [ZJOI2010] 贪吃的老鼠，所以去掉那道题的二分即可 AC。

这里说一下更简单的建边方式：

首先将所有 p_i 和 k_i 离散化，将整个时间划分为 O(n) 个区间，那么一个任务必然可以用若干个时间区间拼接出来。

然后设 m 个处理器对应点 1\sim m，n 个任务对应点 m+1 \sim m+n。

源点向每个处理器连 INF 边，第 i 个任务向汇点连容量为 c_i 的边。

然后考虑如何处理处理器与任务之间的边，我们可以对第 i 个时间段建一个点 n+m+i，同时可以计算这个时间段经过的时间 t_i，每个处理器向这个点连一条容量为 t_i 的边，代表处理器可以处理的时间，这个点对于每一个包含这个时间段的任务也连一条容量为 t_i 的边，代表这个时间段最多被处理器处理多久。

可以发现，在题目的条件下，跑出的流一定可以对应一个分配处理器的合法方案，即满足题目中一个处理器同一时间只能处理一个任务，一个任务同一时间只能在一个处理器上被处理的限制。

于是跑完最大流后检查一下是否满流就可以了。

时间复杂度 O(n^3(n+m))，实际远远跑不满。

code

代码中的变量定义与题目中略有不同。

// by MornStar
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=405,M=100505,INF=0x3f3f3f3f3f3f3f3f;
//N: max of node num
//M: max of edge num
//T: the type of max_flow
//INF: max of max_flow
//eps: is used to check the val is 0 or not
template<int N,int M,typename T,const T INF=0x3f3f3f3f,const T eps=0>
struct Dinic{
    const int inf=0x3f3f3f3f;
    int vnum,s,t;
    struct edge{int to,pre;T w;}e[M<<1];
    int head[N],now[N],cnt=1;
    //use opt=1 to add undirected edge
    void add_edge(int u,int v,T w=INF,int opt=0){
        e[++cnt]={v,head[u],w};head[u]=cnt;
        e[++cnt]={u,head[v],w*opt};head[v]=cnt;
    }
    int dis[N];
    queue<int>q;
    void set_information(int num,int _s,int _t){vnum=num,s=_s,t=_t;}
    void set_dis(){for(int i=1;i<=vnum;i++) dis[i]=inf;}
    void clear(){cnt=1,clear_head(),set_information(0,0,0);}
    void clear_head(){for(int i=1;i<N;i++)  head[i]=0;}
    void clear_q(){while(!q.empty())    q.pop();}
    bool bfs(){
        clear_q(),set_dis();
        dis[s]=0,now[s]=head[s];q.push(s);
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=head[x];i;i=e[i].pre){
                edge &it=e[i];
                if(it.w>eps&&dis[it.to]==inf){
                    dis[it.to]=dis[x]+1;
                    q.push(it.to),now[it.to]=head[it.to];
                    if(it.to==t)    return 1;
                }
            }
        }
        return 0;
    }
    T dinic(int x,T flow){
        if(x==t)    return flow;
        T ret=0;
        for(int i=now[x];i&&(flow>eps);i=e[i].pre){
            now[x]=i;
            edge &it=e[i],&rev=e[i^1];
            if(it.w>eps&&(dis[it.to]==dis[x]+1)){
                T k=dinic(it.to,min(flow,it.w));
                if(!k)  dis[it.to]=inf;
                it.w-=k,rev.w+=k,flow-=k,ret+=k;
            }
        }
        return ret;
    }
    T max_flow(){
        T ret=0;
        while(bfs())    ret+=dinic(s,INF);
        return ret;
    }
    T min_cut(){return max_flow();}
    //upper and lower bound flow
    bool check_full(){
        for(int i=head[s];i;i=e[i].pre){
            if(e[i].w>eps)  return 0;
        }
        return 1;
    }
    void debug(){
        for(int i=2;i<=cnt;i+=2)    cerr<<e[i^1].to<<' '<<e[i].to<<" "<<e[i].w<<"\n";
    }
};
Dinic<N,M,ll,INF>dc;
int n,m,l[N],r[N],t[N],b[N<<1],tb,num;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>l[i]>>r[i]>>t[i],num+=t[i],b[++tb]=l[i],b[++tb]=r[i];
    sort(b+1,b+tb+1);
    tb=unique(b+1,b+tb+1)-b-1;
    dc.set_information(N-1,N-2,N-1);
    for(int i=1;i<=m;i++)   dc.add_edge(dc.s,i,INF);
    for(int i=1;i<=n;i++)   dc.add_edge(m+i,dc.t,t[i]);
    for(int i=1;i<tb;i++){
        for(int j=1;j<=m;j++)   dc.add_edge(j,n+m+i,b[i+1]-b[i]);
        for(int j=1;j<=n;j++){
            if(l[j]<=b[i]&&b[i+1]<=r[j])    dc.add_edge(n+m+i,m+j,b[i+1]-b[i]);
        }
    }
//  dc.debug();
    int ans=dc.max_flow();
    if(ans==num)    cout<<"TAK\n";
    else    cout<<"NIE\n";
}