Clever King (最大权闭合子图模板)

2018-04-23

Clever King

题意

T组数据，有n个产品，m个矿坑。接下来n个数字happiness[i]表示第i个产品的幸福指数，接下来m个数字，ori[i]表示第i个矿坑的开发费用。接下来n行，每行先输入两个数字n1，n2，分别表示第i号产品需要开发的矿坑，和需要的原材料产品。（矿坑开发后材料无限，产品生产后幸福指数一定会增加，不管是作为产品本身还是原材料），要求幸福指数 - 费用的最大值。

思路

最大权闭合子图模板。【关于网络流】（ND）

定义

一个子图（点集），如果它的所有的出边都在这个子图当中，那么它就是闭合子图。
点权和最大的闭合子图就是最大闭合子图。

简单说就是有一些点，每个点有一些点权（正负都有），要选一个点，就必须要选它所连向的点。

有可能连成一条链，像这样：x->y->z->…

求合法的点集的最大的点权和。

构图

设s为源点，t为汇点。

使s连向所有的正权点（非负权点），边权为点权。

使所有非负权点（负权点）连向t，边权为点权的绝对值。

若需要选y才能选x，连一条由x到y的边，边权是∞。

最大点权和 = 正权点和 - 最小割

看！代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=505;
struct node{
    int to,next,flow;
}e[maxn*maxn*2];
int cur[maxn],co[maxn],d[maxn],Final[maxn],tot,s,t;
// s源点 t终点

void link(int x,int y,int z)
{
    e[++tot].to=y,e[tot].next=Final[x],e[tot].flow=z,Final[x]=tot;
    e[++tot].to=x,e[tot].next=Final[y],e[tot].flow=0,Final[y]=tot;
}
int dg(int x,int flow) //模板 
{
    if(x==t) return flow;
    int use=0;
    for(int i=cur[x];i;i=e[i].next)
    {
        cur[x]=i;
        if(e[i].flow>0&&d[e[i].to]+1==d[x])
        {
            int c=dg(e[i].to,min(flow-use,e[i].flow));
            use+=c;
            e[i].flow-=c;
            e[i^1].flow+=c;
            if(flow==use) return use;
        }
    }
    cur[x]=Final[x];
    if(!(--co[d[x]])) d[0]=t;
    ++co[++d[x]];
    return use;
}
int main()
{
    int T,n1,n2,temp,n,m;
    int ans;
    long long sum;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;tot=1;s=t=0;
        memset(cur,0,sizeof(cur));
        memset(co,0,sizeof(co));
        memset(d,0,sizeof(d));
        memset(Final,0,sizeof(Final));
        scanf("%d%d",&n,&m);
        ans=n+m;s=ans+1;t=ans+2;
        for(int i=1;i<=n;i++) //s和正权相连
        {
            scanf("%d",&temp);
            sum+=temp;
            link(s,i,temp);
        }
        for(int i=1;i<=m;i++)  //t和负权相连
        {
            scanf("%d",&temp);
            link(i+n,t,temp);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&n1,&n2);
            for(int j=1;j<=n1;j++)  //i个点需要j的话，就把i->j，边权是inf
            {
                scanf("%d",&temp);
                link(i,temp+n,1<<30);
            }
            for(int j=1;j<=n2;j++)
            {
                scanf("%d",&temp);
                link(i,temp,1<<30);
            }
        }
        co[0]=t;
        for(;d[0]<t;) sum-=dg(s,1<<30); //最小割
        printf("%lld\n",sum);
    }
    return 0;
}