P3410 拍照 题解

原题目链接

每张合影可选可不选，选了必须带一些特定人：明显的最大权闭合子图

最大权闭合子图：

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

经典的网络流问题，具体使用最小割求解。

根据最大流最小割定理，最大流=最小割，所以这题可以使用最大流算法求解

我们将合影和人都看成一个点，然后如下建边：

1. 源点向合影连流量为利润的边

2. 人向汇点连流量为花费的边

3. 每个合影向需要的人连流量为inf的边

接下来我们思考这样建边的正确性

在最小割模型中，连一条流量为$inf$的边意为连一条不可割边

那么这个图中的可割边就只有合影和人了

跑最大流（最小割）即为计算最优方案下的花费

最终答案（最大净利润）为全部合影能赚到的钱减去最小割

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
const int inf=1e9;
const int N=3e5+1;
struct edge
{
    int from,to,next,cap,flow;
}e[N];
int cnt,n,m,sour,sink,head[N],ans,q[N],l[N],p[N];
inline int min(int i,int j)
{
    return i<j?i:j;
}
inline void add(int u,int v,int l)
{
    e[++cnt]=(edge){u,v,head[u],l,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].next)
            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 true;
            }
    }
    return false;
}
int dfs(int x,int now)
{
    if(x==sink||!now)
        return now;
    int t=now,detla;
    for(int i=head[x];i;i=e[i].next)
    {
        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);
}
inline void read(int &x)
{
    char ch=getchar();
    int f=1;
    x=0;
    while(!('0'<=ch&&ch<='9'))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    do
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }while('0'<=ch&&ch<='9');
    x*=f;
}
int main()
{
    read(m);
    read(n);
    int res=0;
    sour=0;
    sink=m+n+1;
    for(int i=1;i<=m;i++)
    {
        int val,x;
        read(val);
        res+=val;//计算总收益
        add(sour,i,val);
        read(x);
        while(x!=0)
        {
            add(i,x+m,inf);
            read(x);
        }
    }
    for(int i=m+1;i<=n+m;i++)
    {
        int val;
        read(val);
        add(i,sink,val);
    }
    dinic();
    printf("%d",res-ans);//ans即为总花费
    return 0;
}

双倍经验：P2762 太空飞行计划问题，快去骗经验啊qwq