P4177 [CEOI2008]order 题解

原题目链接

先无视租机器，明显的最大权闭合子图

最大权闭合子图：

给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

我们将机器和任务都看成一个点

如果这题没有租机器，这题的建边方式就应该是这样：

1. 源点向订单连流量为利润的边

2. 机器向汇点连流量为购买价格的边

3. 每个订单向需要的机器连流量为inf的边

可以发现，源点连的边都是订单的利润，汇点连的边都是机器的成本，只有机器和订单之间的边是$inf$

对于每个订单需要的相同机器，租用的价格也不一样

所以我们考虑把$inf$换成租机器的费用

从正确性的角度考虑，跑最大流（最小割）是计算最优方案下的成本，若总租借费用低于购买机器费用，表示购买费用的那条边就不会满流，防止购买机器反而增加成本；反之表示购买费用的那条边就会满流，限制住成本因多次租用同一机器而增加

最终建边方式如下：

1. 源点向订单连流量为利润的边

2. 机器向汇点连流量为购买价格的边

3. 每个订单向需要的机器连流量为租用费用的边

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x)
{
    int ch=getchar();
    T f=1;
    x=0;
    while(!('0'<=ch&&ch<='9'))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    x*=f;
}
const int inf=1e9,N=3e5+1;
struct edge
{
    int from,to,nxt,cap,flow;
}e[N*20];
int cnt,n,m,sour,sink,head[N],ans,q[N],l[N],p[N];
inline void add(const int &u,const int &v,const int &f)
{
    e[++cnt]=(edge){u,v,head[u],f,0};
    head[u]=cnt;
    e[++cnt]=(edge){v,u,head[v],0,0};
    head[v]=cnt;
}
inline bool find()
{
    memset(l,0,sizeof(l));
    int h=1,t=1;
    q[1]=sour;
    l[sour]=1;
    while(h<=t)
    {
        int x=q[h++];
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(!l[e[i].to]&&e[i].cap>e[i].flow)
            {
                q[++t]=e[i].to;
                l[e[i].to]=l[x]+1;
                if(e[i].to==sink)
                    return 1;
            }
        }
    }
    return 0;
}
int dfs(const int &x,const int &now)
{
    if(x==sink||!now)
        return now;
    int t=now,detla;
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].cap>e[i].flow&&l[e[i].to]==l[x]+1)
        {
            detla=dfs(e[i].to,min(t,e[i].cap-e[i].flow));
            if(!detla)
                l[e[i].to]=0;
            e[i].flow+=detla;
            e[((i-1)^1)+1].flow-=detla;
            t-=detla;
            if(t==0)
                break;
        }
    }
    return now-t;
}
inline void dinic()
{
    while(find())
        ans+=dfs(sour,inf);
}
int main()
{
    read(n);
    read(m);
    sour=0;
    sink=n+m+1;
    int u,v,t,r,tot=0;
    for(int i=1;i<=n;++i)
    {
        read(v);
        read(t);
        add(sour,i,v);
        for(int j=1;j<=t;++j)
        {
            read(u);
            read(r);
            add(i,u+n,r);
        }
        tot+=v;
    }
    for(int i=1;i<=m;++i)
    {
        read(v);
        add(i+n,sink,v);
    }
    dinic();
    printf("%d",tot-ans);
    return 0;
}