P2762 太空飞行计划问题网络流最大权闭合图

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入输出格式

输入格式：

第1行有2 个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

输出格式：

第1 行是实验编号；第2行是仪器编号；最后一行是净收益。

以下内容参考胡伯涛《最小割模型在信息学竞赛中的应用》，感谢他为我们提供这么优秀的论文。

这道题是最大权闭合图。

对于每个实验，连一条从s到实验，边权为实验利益的边。
对于每个需要的仪器，连一条从实验到器材，边权为INF的边。
对于每个仪器，连一条从器材到t，边权为器材耗费的边。

按照上面建图，求最小割即最大流，然后用实验利益总和减去最大流即为最大净收益，具体证明可以在论文中查阅。

输出方案的时候和我之前的认知产生了偏差如果使用的话那么正向边为0 反向边跑满但是这题按照这个结论一直wa

可以采用分层图的等级来写 level ！=0 说明使用

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=4e5+44;
const int M=4e6+54;

struct edge {
    int to, next, w;
} e[M << 1];
int head[N], cnt = 1;
void init()
{
    cnt=1;CLR(head,0);
}
void add(int x, int y, int z) {
    e[++cnt] = (edge){y, head[x], z};
    head[x] = cnt;
    e[++cnt] = (edge){x, head[y], 0};
    head[y] = cnt;
}
int level[N];
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int i = head[pos]; i; i = e[i].next) {
            int nx = e[i].to;
            if (!e[i].w || level[nx]) continue;
            level[nx] = level[pos] + 1;
            q.push(nx);
        }
    }
    return level[t];
}
int dfs(int s, int t, int flow) {
    if (s == t) return flow;
    int ret = 0;
    for (int i = head[s]; flow && i; i = e[i].next) {
        int nx = e[i].to;
        if (level[nx] == level[s] + 1 && e[i].w) {
            int tmp = dfs(nx, t, min(flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            flow -= tmp;
            ret += tmp;
        }
    }
    if (!ret) level[s] = 0;
    return ret;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) ret += dfs(s, t, inf);
    return ret;
}
int n,m,s,t,node[N],sum,cost[N];
vector<int>table[N];
char c[N];
int main()
{
    RII(n,m);
    rep(i,1,n)
    {
        RI(node[i]);
        sum+=node[i];
         memset(c,0,sizeof(c));
        cin.getline(c,10000);
        int ulen=0,num;
        while (sscanf(c+ulen,"%d",&num)==1)
        {
            add(i,n+num,inf);
            if (num==0) ulen++;
            else while (num)
            {
                num/=10;
                ulen++;
            }
            ulen++;
        }
    }
    s=n+m+10,t=s+1;
    rep(i,1,m)RI(cost[i]);

    rep(i,1,n)
    {
        add(s,i,node[i]);
    }
    rep(i,1,m)add(n+i,t,cost[i]);

    int ans=dinic(s,t);

    rep(i,1,n)
    if(level[i])printf("%d ",i);

    cout<<endl;
    rep(i,n+1,n+m)
    if(level[i])printf("%d ",i-n);

    cout<<endl<<sum-ans;
    return 0;
}

View Code

最大权闭合图的固定连法:

s连所有的利益点值为收益大小

损失点连t

每个点连其前提

答案为所有收益