原题链接

Description

有m(m≤50)个实验和n(n≤50)个仪器，做实验有报酬买仪器有花费。每个实验都需要一些仪器，求最大净收益（实验报酬−仪器花费），并输出一组方案。

Solution

实验向所需仪器连边，实验的点权是其报酬，仪器的点权是其花费的相反数，这样构成一张带权图。所求的就是这个图的最大权闭合图。

关于最大权闭合图的求法及其证明，请参照胡泽涛的《最小割模型在信息学竞赛中的应用》P16。

Code

//「网络流 24 题」太空飞行计划

#include <cstdio>

#include <cstring>

int const N=100+10;

int const INF=0x7FFFFFFF;

int m,n;

int s,t; int cnt,h[N];

struct edge{int v,c,nxt;} ed[N*N];

void edAdd(int u,int v,int c)

{

    cnt++; ed[cnt].v=v,ed[cnt].c=c,ed[cnt].nxt=h[u],h[u]=cnt;

    cnt++; ed[cnt].v=u,ed[cnt].c=0,ed[cnt].nxt=h[v],h[v]=cnt;

}

int dpt[N]; int op,cl,q[N];

bool bfs()

{

    op=cl=0; memset(dpt,0,sizeof dpt);

    dpt[q[++cl]=s]=1;

    while(op<cl)

    {

        int u=q[++op]; if(u==t) break;

        for(int i=h[u];i;i=ed[i].nxt)

        {

            int v=ed[i].v,c=ed[i].c;

            if(!dpt[v]&&c) dpt[q[++cl]=v]=dpt[u]+1;

        }

    }

    return dpt[t];

}

int min(int x,int y) {return x<y?x:y;}

int fill(int u,int in)

{

    if(u==t||in==0) return in;

    int out=0;

    for(int i=h[u];i;i=ed[i].nxt)

    {

        int v=ed[i].v,c=ed[i].c;

        if(dpt[v]!=dpt[u]+1||!c) continue;

        int fl=fill(v,min(c,in-out));

        if(!fl) dpt[v]=0;

        else out+=fl,ed[i].c-=fl,ed[i^1].c+=fl;

        if(in==out) return out;

    }

    return out;

}

int Dinic()

{

    int ans=0;

    while(bfs()) ans+=fill(s,INF);

    return ans;

}

bool buy[N];

int main()

{

    scanf("%d%d",&m,&n); s=0,t=n+m+1; cnt=1;

    int ans=0;

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

    {

        int c=0; scanf("%d",&c);

        ans+=c; edAdd(s,i,c);

        while(true)

        {

            char ch=getchar(); if(ch=='\n'||ch=='\r') break;

            int x; scanf("%d",&x); edAdd(i,m+x,INF);

        }

    }

    for(int i=1;i<=n;i++) {int c; scanf("%d",&c); edAdd(m+i,t,c);}

    ans-=Dinic();

    for(int i=1;i<=m;i++) if(dpt[i]) printf("%d ",i); printf("\n");

    for(int i=1;i<=n;i++) if(dpt[i+m]) printf("%d ",i); printf("\n");

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

    return 0;

}

P.S.

又是鬼畜的输入格式…