牛客勤奋的杨老师（二）(最大权闭合子图)

链接：https://ac.nowcoder.com/acm/problem/15828
来源：牛客网

题目描述

众所周知，杨老师是一位十分勤奋的老师，他非常的热爱学习。

勤奋的他为自己罗列了一个学习清单，共有n个知识点，他可以有选择的进行学习。

每个知识点都会对应0个或1个或多个先修知识点（只有学会了先修知识点才能学习该知识点），同时每个知识点都有一个智慧值和一个智力消耗值。

杨老师希望在进行过激烈的学习之后，他的收获可以·量化为所有学过的题的智慧值的和与智力消耗值的和的差值。请问，这个值最大是多少？

输入描述:

第一行：一个整数n（n<=500）接下来n行，每行两个整数，代表第i个知识点的智慧值和智力消耗值接下来若干行，每行2个整数u, v，代表u是v的先修知识点。

输出描述:

一行，表示杨老师的收获的最大值

示例1

输入

复制

输出

复制

最大权闭合子图讲解 https://www.cnblogs.com/dilthey/p/7565206.html

https://blog.csdn.net/can919/article/details/77603353

比较模板的题

定义

有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。

最小割=(不选的正权之和+要选的负权绝对值之和）
最大权闭合子图=（正权之和-不选的正权之和-要选的负权绝对值之和）=正权值和-最小割
因为正权值和，是定值，而最小割保证值最小，所以最大权闭合子图一定最优。

当然这道题是要求前继反向建边即可

建图时正权值接源点负权值的绝对值接汇点

正权之和减去最小割（最大流）即为结果

#include<queue>
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int  inf=1e9+7;
const int maxn=2e4+10;
const int maxm=5e4+10;
struct Edge
{
    int v,f,nxt;
};
int n,src,sink;
int g[maxn+10];
int nume;
Edge e[maxm*2+10];
void addedge(int u,int v,int c)
{
    e[++nume].v=v;
    e[nume].f=c;
    e[nume].nxt=g[u];
    g[u]=nume;
    e[++nume].v=u;
    e[nume].f=0;
    e[nume].nxt=g[v];
    g[v]=nume;
}

queue<int>que;
bool vis[maxn+10];
int dist[maxn+10];
int N,F,D;
void bfs()
{
    memset(dist,0,sizeof(dist));
    while(!que.empty())que.pop();
    vis[src]=true;
    que.push(src);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=g[u]; i; i=e[i].nxt)
        {
            if(e[i].f&&!vis[e[i].v])
            {
                que.push(e[i].v);
                dist[e[i].v]=dist[u]+1;
                vis[e[i].v]=true;
            }
        }
    }
}
int dfs(int u,int delta)
{
    if(u==sink)
        return delta;
    else
    {
        int ret=0;
        for(int i=g[u]; delta&&i; i=e[i].nxt)
        {
            if(e[i].f&&dist[e[i].v]==dist[u]+1)
            {
                int dd=dfs(e[i].v,min(e[i].f,delta));
                e[i].f-=dd;
                e[i^1].f+=dd;
                delta-=dd;
                ret+=dd;
            }
        }
        return ret;
    }
}
int maxflow()
{
    int ret=0;
    while(1)
    {
        memset(vis,0,sizeof(vis));
        bfs();
        if(!vis[sink])return ret;
        ret+=dfs(src,inf);
    }
}
int a[maxn];
void init()
{
    memset(g,0,sizeof(g));
    nume=1;
    int n,x,y;
    scanf("%d",&n);
    src=n+1;
    sink=n+2;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        a[i]=x-y;
        if(a[i]<0)
            addedge(i,sink,-a[i]);
        else addedge(src,i,a[i]),ans+=a[i];
    }


    while(scanf("%d%d",&x,&y)!=EOF)
    {
       if(x==-1)
        break;
       addedge(y,x,inf);
    }
    cout<<ans-maxflow();

}
int main()
{
    init();
    return 0;
}