题解 P4177 【[CEOI2008]order】

· · 题解

Youngsc
首先如果没有租用机器这种鬼畜的操作，那么就是一个裸的最大权闭合子图例如 太空飞行计划
但是有了租用这种操作显然就那样来解决这个问题了
普通的最大权闭合子图将工作与源相连，容量为收益，机器与汇相连，容量为代价的相反数，对应的工作与机器之间是无穷大
这样割掉与源点或汇点相连的边表示选择失去那种利益
感性认识一下，租用机器这种操作仅仅只会对一种工作产生影响，无论其他工作是否需要它
那么启发我们是不是可以用中间工作与机器的相连的边搞一些事情
我们将工作与机器之间的边容量由正无穷变为租用的代价即可处理租用问题
原理就是最大权闭合子图问题的实质是割掉一些边使源和汇不连通
考虑源和汇之间的一条路径，有三种选择，对应割掉三条边
显然个点左右两条边可以影响其他的路径，而割掉中间不会 因此我们就可以将中间的边转化为租用操作 其他的就和普通的最大权闭合子图一毛一样了

代码

# include <bits/stdc++.h>
# define LL long long
# define R register
# define N 1210
# define inf 2000101900
using namespace std;

int n,s,t,e=-1,h[N*2],ans,used[N*2],tot,d,w,m,num;
struct zx{int v,flow,pre;} ed[2000010];
int v[N*2];
queue <int> q;

template <typename T> inline void in(R T& a){
    R char c=getchar(); R T x=0,f=1;
    while (!isdigit(c)) {if (c == '-') f=-1; c=getchar();}
    while (isdigit(c)) x = (x<<1)+(x<<3)+c-'0', c=getchar();
    a = x*f;
}

inline void add(R int x,R int y,R int z){
    ed[++e] = (zx){y,z,h[x]};
    h[x] = e;
}

inline bool bfs(){
    for(R int i=0; i<=t; ++i) v[i] = 0;
    v[0] = 1;
    q.push(0);
    while(!q.empty()){
        R int x=q.front();
        q.pop();
        for(R int i=h[x]; i!=-1; i=ed[i].pre)
        {
            R int p=ed[i].v;
            if(ed[i].flow&&!v[p])
            {
                v[p] = v[x]+1;
                q.push(p);
            }
        }
    }
    return v[t];
}

inline int maxflow(R int x,R int want){
    if(x==t||!want) return want;
    R int flow = 0;
    for(R int i=used[x]; i!=-1; i=ed[i].pre,used[x]=i)
    {
        R int p=ed[i].v;
        if(!ed[i].flow||v[p] != v[x]+1) continue;
        R int f=maxflow(p,min(want,ed[i].flow));
        if(!f) continue;
        ed[i].flow -= f;
        ed[i^1].flow += f;
        flow += f;
        want -= f;
    }
    return flow;
}

int main(){
    in(n),in(m);
    s = 0,t = n+m+1;
    for (R int i=s; i<=t; ++i) h[i] = -1;
    for (R int i=1; i<=n; ++i)
    {
        in(w); add(s,i,w),add(i,s,0);
        tot += w;
        in(num);
        while (num--)
        {
            in(d),in(w);
            add(i,d+n,w),add(d+n,i,0);
        }
    }
    for (R int i=1; i<=m; ++i) in(w), add(n+i,t,w),add(t,n+i,0);
    while (bfs()){
        memcpy(used,h,sizeof(h));
        ans += maxflow(s,inf);
    }
    printf("%d\n",tot-ans);
    return 0;
}