POJ

传送门

最小割模型在信息学竞赛中的应用

公司要裁员，每个员工有个价值，裁了一个员工必须裁它的下属，问能得到最大价值和该价值下最小裁的员工数。

最大权闭合子图的模板题。

//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
const int N=120007;
typedef long long LL;
const LL inf=1e18; 
using namespace std;
int n,m,num;

template<typename T>void read(T &x)  {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

struct edge{
    int from,to,nx;
    LL cap,flow;
    edge(){}
    edge(int from,int to,LL cap,LL flow,int nx):from(from),to(to),cap(cap),flow(flow),nx(nx){}
}e[N];

int ecnt=1,fir[N];
void add(int u,int v,LL cap) {
    e[++ecnt]=edge(u,v,cap,0,fir[u]); fir[u]=ecnt;
    e[++ecnt]=edge(v,u,0,0,fir[v]); fir[v]=ecnt;
}

queue<int>que;
int c[N],d[N],cur[N],p[N];
void bfs(int s,int t) {
    for(int i=0;i<=num;i++) d[i]=num,c[i]=0;
    que.push(t); d[t]=0;
    while(!que.empty()) {
        int x=que.front();
        que.pop();
        for(int i=fir[x];i;i=e[i].nx) {
            int y=e[i].to;
            if(d[y]==num&&e[i].cap==0) {
                d[y]=d[x]+1;
                que.push(y);
            }
        }
    } 
}

LL cal(int s,int t) {
    LL fl=inf;
    for(int i=t;i!=s;i=e[p[i]].from)
        fl=min(fl,e[p[i]].cap-e[p[i]].flow);
    for(int i=t;i!=s;i=e[p[i]].from) 
        e[p[i]].flow+=fl,
        e[p[i]^1].flow-=fl;
    return fl;
}

LL ISAP(int s,int t) {
    bfs(s,t);
    LL res=0;
    for(int i=1;i<=num;i++) c[d[i]]++,cur[i]=fir[i];
    for(int x=s;d[x]<num;) {
        if(x==t) {
            res+=cal(s,t);
            x=s;
        } 
        int ok=0;
        for(int &i=cur[x];i;i=e[i].nx) 
            if(e[i].flow<e[i].cap&&d[e[i].to]+1==d[x]) {
                ok=1; p[x=e[i].to]=i; break;
            }
        if(!ok) {
            cur[x]=fir[x]; int M=n;
            for(int i=fir[x];i;i=e[i].nx) 
                if(e[i].flow<e[i].cap) M=min(M,d[e[i].to]+1);
            if(!(--c[d[x]])) break;
            c[d[x]=M]++;
            if(x!=s) x=e[p[x]].from;
        }
    }
    return res;
}

int vis[N]; 
LL ansnum;
int dfs(int x) {
    for(int i=fir[x];i;i=e[i].nx) 
        if(e[i].flow<e[i].cap&&!vis[e[i].to]) {
            ansnum++; 
            vis[e[i].to]=1;
            dfs(e[i].to);
        }
}

int main() {
    read(n); read(m);
    int s=n+1,t=s+1;
    LL ansmx=0; num=t;
    for(int i=1;i<=n;i++) {
        int x; read(x);
        if(x>0) add(s,i,x),ansmx+=x;
        else add(i,t,-x);
    }
    for(int i=1;i<=m;i++) {
        int u,v;
        read(u); read(v);
        add(u,v,inf);
    }
    ansmx-=ISAP(s,t);
    vis[s]=1; dfs(s);
    printf("%lld %lld
",ansnum,ansmx);
    return 0;
}