BZOJ_1391_[Ceoi2008]order_最大权闭合子图

Description

有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。现在给出这些参数，求最大利润

Input

第一行给出 N,M(1<=N<=1200,1<=M<=1200) 下面将有N块数据，每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序接下来若干行每行两个数，分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000]) 最后M行，每行给出购买机器的费用(其在[1,20000])

Output

最大利润

Sample Input

2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110

Sample Output

权值有正有负，很容易想到最大权闭合子图。

S连工序-利润代表割这个就不选这个任务

任务连机器-租的费用代表这个付出租的代价

机器连T-购买的费用代表付出购买的费用。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 2500

#define M 3600050

#define S (n+m+1)

#define T (n+m+2)

#define inf 100000000

int head[N],to[M],nxt[M],flow[M],cnt=1,dep[N],Q[N],l,r,sum,n,m,cur[N];

inline void add(int u,int v,int f) {

    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f;

    to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0;

}

bool bfs() {

    int i;

    memset(dep,0,sizeof(dep)); l=r=0;

    Q[r++]=S; dep[S]=1;

    while(l<r) {

        int x=Q[l++];

        for(i=head[x];i;i=nxt[i]) {

            if(!dep[to[i]]&&flow[i]) {

                dep[to[i]]=dep[x]+1;

                if(to[i]==T) return 1;

                Q[r++]=to[i];

            }

        }

    }

    return 0;

}

int dfs(int x,int mf) {

    if(x==T) return mf;

    int nf=0,i;

    for(i=cur[x];i;i=nxt[i]) {

        if(dep[to[i]]==dep[x]+1&&flow[i]) {

            int tmp=dfs(to[i],min(mf-nf,flow[i]));

            if(!tmp) dep[to[i]]=0;

            nf+=tmp;

            flow[i]-=tmp;

            if(flow[i]) cur[x]=i;

            flow[i^1]+=tmp;

            if(nf==mf) break;

        }

    }

    return nf;

}

void dinic() {

    int ans=sum,f,i;

    while(bfs()) {

        for(i=1;i<=T;i++) cur[i]=head[i];

        while(f=dfs(S,inf)) ans-=f;

    }

    printf("%d\n",ans);

}

int main() {

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

    int i,x,y,z,w;

    for(i=1;i<=n;i++) {

        scanf("%d%d",&x,&y);

        add(S,i,x);

        sum+=x;

        while(y--) {

            scanf("%d%d",&z,&w);

            add(i,z+n,w);

        }

    }

    for(i=1;i<=m;i++) {

        scanf("%d",&x);

        add(i+n,T,x);

    }

    dinic();

}

秒客网