最大权闭合子图的权值等于所有正权点之和减去最小割。

这次求最大流时犯了一个错误呀-.-  递归中竟然用了一个外部变量来转换--- 递归后量就变了---坑了自己一下午

Dinic 算法 ：每次求可行流量时先bfs一下，然后dfs时对于边 ( w - u) 只考虑 u 的深度大于 w 的边就行dfs 。比Ford-Fulkerson快了好多---

Ford-Fulkerson代码：

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    int to,cap,fac;
}Q;
vector<node> V[4200];
bool fafe[4200];
void add_edge(int a,int b,int c)
{
    Q.to=b;Q.cap=c;Q.fac=V[b].size();
    V[a].push_back(Q);
    Q.to=a;Q.cap=0;Q.fac=V[a].size()-1;
    V[b].push_back(Q);
}
int mi_graph(int s,int t,int ans)
{
    if (s==t) return ans;
    fafe[s]=true;
    int v;
    for (int i=0;i<V[s].size();i++)
    {
        if (fafe[V[s][i].to]||V[s][i].cap==0) continue;
        v=mi_graph(V[s][i].to,t,min(ans,V[s][i].cap));
        if (v)
        {
            V[s][i].cap-=v;
            V[V[s][i].to][V[s][i].fac].cap+=v;
            return v;
        }
    }
    return 0;
}
int main()
{
    int n,m,s,t,a,b,MIX=0x3f3f3f3f,ans;
    while (~scanf("%d%d",&n,&m))
    {
        s=0;t=n+m+1;ans=0;
        for (int i=0;i<=t;i++)
            V[i].clear();
        for (int i=1;i<=m;i++)
        {
            cin>>a;
            add_edge(i+n,t,a);
        }
        for (int i=1;i<=n;i++)
        {
            cin>>a;
            ans+=a;
            add_edge(s,i,a);
            cin>>b;
            while (b--)
            {
                cin>>a;
                add_edge(i,a+n,MIX);
            }
        }
        int k=1;
        while (k)
        {
            memset(fafe,false,sizeof(fafe));
            k=mi_graph(s,t,MIX);
            ans-=k;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Dinic代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
struct node{
    int to,cap,fac;
}Q;
vector<node> V[420];
bool fafe[420];
int level[420];
void add_edge(int a,int b,int c)
{
    Q.to=b;Q.cap=c;Q.fac=V[b].size();
    V[a].push_back(Q);
    Q.to=a;Q.cap=0;Q.fac=V[a].size()-1;
    V[b].push_back(Q);
}
int dfs(int s,int t,int MIX)
{
    if (s==t) return MIX;
    for (int i=0;i<V[s].size();i++)
    {
        /*Q=V[s][i];
        if (level[Q.to]>level[s]&&Q.cap!=0)
        {
            int ls=dfs(Q.to,t,min(MIX,Q.cap));
            if (ls)
            {
                V[s][i].cap-=ls;
                V[Q.to][Q.fac].cap+=ls;
                return ls;
            }
        }*/
        if (level[V[s][i].to]>level[s]&&V[s][i].cap!=0)
        {
            int ls=dfs(V[s][i].to,t,min(MIX,V[s][i].cap));
            if (ls)
            {
                V[s][i].cap-=ls;
                V[V[s][i].to][V[s][i].fac].cap+=ls;
                return ls;
            }
        }
    }
    return 0;
}
int mi_graph(int s,int t,int MIX)
{
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    int v;
    que.push(s);
    while (!que.empty())
    {
        v=que.front();
        que.pop();
        for (int i=0;i<V[v].size();i++)
        {
            Q=V[v][i];
            if (level[Q.to]!=-1||Q.cap==0) continue;
            que.push(Q.to);
            level[Q.to]=level[v]+1;
        }
    }
    if (level[t]==-1)
        return 0;
    int ans=1,sum=0;
    while (ans)
    {
        ans=dfs(s,t,MIX);
        sum+=ans;
    }
    return sum;
}
int main()
{
    int n,m,s,t,a,b,ans,ss,MIX;
    MIX=INF;
    scanf("%d%d",&n,&m);
    s=0;t=n+m+1;ans=0;
    for (int i=0;i<=t;i++)
        V[i].clear();
    for (int i=1;i<=m;i++)
    {
        cin>>a;
        add_edge(i+n,t,a);
    }
    for (int i=1;i<=n;i++)
    {
        cin>>a;
        ans+=a;
        add_edge(s,i,a);
        cin>>b;
        while (b--)
        {
            cin>>a;
            add_edge(i,a+n,MIX);
        }
    }
    int k=1;ss=0;
    while (k)
    {
        k=mi_graph(s,t,MIX);
        ss+=k;
    }
    cout<<ans-ss<<endl;
    return 0;
}

hiho一下 第119周 #1398 : 网络流五·最大权闭合子图 【最小割-最大流--Ford-Fulkerson 与 Dinic 算法】