GMOJ 2429. 【NOI2008】志愿者招募 题解

思路

oh，我可爱的一眼网络流题。

话说为什么一天一道网络流

这个做法好像比较清奇。

非常清奇你根本找不到一样的

之前口胡过最长 k 可重区间集 ，所以很快就有思路了。

首先对于区间 \([l,r]\) ，我们把 \(l\) 与 \(r+1\) 连一条无限流量输入费用的边。

然后考虑因为是至少覆盖所以志愿者（流量）不能在区间不覆盖时移动，但是显然区间会重。

于是我们对于每一个点 \(i\) 向 \(i-1\) 连一条无限流量无费用的边，让流量可以在两个重叠区间中移动。

再考虑每天人数不一样，这个比较显然，需要就从源点补，多了就退给汇点。

显然汇点直接为 \(n+1\) 这样减少一些处理。

如样例建图为：

graph TD 0((S))--1/0-->2((2)) 0((S))--2/0-->1((1)) 0((S))--1/0-->3((3)) 3((3))--INF/2-->4((T)) 2((2))--INF/5-->4((T)) subgraph 1((1))--INF/2-->3((3)) 2((2))--INF/0-->1((1)) 3((3))--INF/0-->2((2)) end

CODE

因为数据比较大写了一个 SPFA-PMF 核心的 Primal-Dual 原始对偶算法优化 zkw 费用流。

事实证明并不需要。

#include
#include
#include
#include
#define reg register
#define uni unsigned
#define ll long long
using namespace std;
const int N=1010,M=40010,FSIZE=1<<20,INF=0x7f7f7f7f,W=4;
int n,m,d[N<<3],a[N],last,map[N];
struct edge{
    int l,t;ll v,c;
}e[M];
ll ht[N],w[N],mincost;
bool vis[N];
char BuF[FSIZE],*InF=BuF;
templatevoid read(T &x){
    for(;47>*InF||*InF>58;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
void add(int x,int y,int z,ll c){
    e[last]=(edge){a[x],y,z,c};
    a[x]=last++;
}
void Add(int x,int y,int z,ll c){
    add(x,y,z,c);
    add(y,x,0,-c);
}
void spfa(){
    memset(ht,127,sizeof(ht));
    for(reg int h=0,t=ht[0]=0;h<=t;++h){
        reg int hd=d[h];
        for(reg int i=a[hd];~i;i=e[i].l){
            reg int to=e[i].t;ll p=ht[hd]+e[i].c;
            if(e[i].v&&ht[to]>p){
                ht[to]=p;
                if(!vis[to]) vis[d[++t]=to]=1;
            }
        }
        vis[hd]=0;
    }
}
uni seed=time(0);
int rnd(const int &l,const int &r){
    seed^=seed<<17;seed^=seed>>13;seed^=seed>>5;
    return(seed%(r-l+1)+l);
}
void change(int &x,int &y){
    swap(map[x],map[y]);
    swap(x,y);
}
bool spfa_PMF(){
    memset(w,127,sizeof(w));
    for(reg int h=0,t=w[0]=0;h<=t;++h){
        reg int &hd=d[h];
        for(reg int i=0,*zh=d+h+1,*tl=d+t;iw[*zh]) change(hd,*zh);
            if(w[hd]>w[*tl]) change(hd,*tl);
        }
        for(reg int i=a[hd];~i;i=e[i].l){
            reg int to=e[i].t;ll p=w[hd]+e[i].c+ht[hd]-ht[to];
            if(e[i].v&&w[to]>p){
                w[to]=p;
                if(!map[to]){
                    d[map[to]=++t]=to;
                    if(t>h+1&&w[d[t]]>w[d[t-1]]) change(d[t],d[t-1]);
                }else if(w[to]d[i-1]) Add(0,i,d[i]-d[i-1],0);
        else Add(i,n+1,d[i-1]-d[i],0);
    }
    for(reg int x,y,z;m;--m){
        read(x);read(y);read(z);
        Add(x,y+1,INF,z);
    }
    PMF_SSP();
    printf("%lld",mincost);
    return(0);
}