POJ 2987 Firing | 最大权闭合团

一个点带权的图,有一些指向关系,删掉一个点他指向的点也不能留下,问子图最大权值

---

题解:

这是最大权闭合团问题

闭合团:集合内所有点出边指向的点都在集合内

构图方法

1.S到权值为正的点,容量为权值

2.权值为负的点到T,容量为权值绝对值

3.原图所有点容量为INF

4.正权值和-最小割=最大权值

5.S能在残余网络中搜到的点就是删除的点的个数

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

typedef long long ll;

#define N 5010

#define M 120010

#define INF 100000000000000LL

using namespace std;

ll head[N],cur[N],n,m,w[N],S,T,lev[N],ecnt=1,ans,sum,vis[N];

queue <int> q;

struct adj

{

    ll nxt,v,w;

}e[2*M];

void add(ll u,ll v,ll w)

{

    e[++ecnt].v=v,e[ecnt].w=w,e[ecnt].nxt=head[u],head[u]=ecnt;

    e[++ecnt].v=u,e[ecnt].w=0,e[ecnt].nxt=head[v],head[v]=ecnt;

}

inline ll bfs()

{

    ll u,v;

    for (ll i=S;i<=T;i++)

	lev[i]=-1,cur[i]=head[i];

    lev[S]=0,q.push(S);

    while (!q.empty())

    {

	u=q.front();

	for (ll i=head[u];i;i=e[i].nxt)

	{

	    if (e[i].w>0 && lev[v=e[i].v]==-1)

		lev[v]=lev[u]+1,q.push(v);

	}

	q.pop();

    }

    return lev[T]!=-1;

}

inline ll dinic(const ll &u,const ll &flow)

{

    if (u==T) return flow;

    ll res=0,v,delta;

    for (ll &i=cur[u];i;i=e[i].nxt)

    {

	if (e[i].w>0 && lev[u]<lev[v=e[i].v])

	{

	    delta=dinic(v,min(e[i].w,flow-res));

	    if (delta)

	    {

		e[i].w-=delta;

		e[i^1].w+=delta;

		res+=delta;

		if (res==flow) break;

	    }

	}

    }

    if (res!=flow) lev[u]=-1;

    return res;

}

ll Maxflow()

{

    ll ret=0;

    while (bfs())

	ret+=dinic(S,INF);

    return ret;

}

void dfs(ll u)

{

    ll v;

    for (ll i=head[u];i;i=e[i].nxt)

    {

	if (e[i].w>0 && vis[v=e[i].v]==0)

	    vis[v]=1,sum++,dfs(v);

    }

}

int main()

{

    scanf("%lld%lld",&n,&m);

    S=0,T=n+1;

    for (ll i=1,x;i<=n;i++)

    {

	scanf("%lld",&x);

	if (x>0) add(S,i,x),sum+=x;

	else add(i,T,-x);

    }

    for (ll i=1,u,v;i<=m;i++)

	scanf("%lld%lld",&u,&v),add(u,v,INF);

    ans=sum-Maxflow();

    memset(vis,0,sizeof(vis));

    vis[S]=1;

    sum=0;

     dfs(S);

    printf("%lld %lld\n",sum,ans);

    return 0;

}