洛谷 P2762 太空飛行計劃問題 【最小割--最大權閉合子圖】

最大權閉合子圖

定義：

如果對于一個點集合，其中任何一個點都不能到達此集合以外的點，這就叫做閉合子圖。每個點都有一個權值，那麼最大權閉合子圖就是權值最大的那個閉合子圖。

(或者說對于一個點集，這個點集中所有點的出邊所指向的點都在此點集中)

求解

超級源點向每個權值為正的點連邊，容量為該點權值

每個點權為負的點向超級彙點連邊，容量為該點權值相反數

原圖中的邊，容量為inf

然後跑最小割

最後用正點權的總和-最大流即為最大權閉合子圖的權值

證明

蒟蒻自己的了解：

首先按這樣的方式建圖最小割一定是簡單割(隻隔與s,t關聯的邊)

割與s關聯的邊，表示不選這個點，要付出這個點正權值的代價

割與T關聯的邊，表示選這個點，要付出這塊點的負權值的代價

是以最大的閉合圖權值就是總正權值-最小割

形式化的證明，參見——胡伯濤《最小割模型在資訊學競賽中的應用》

時空限制 1000ms / 128MB

題目描述

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行是儀器編号；最後一行是淨收益。

題目分析

超源向每個實驗連邊，容量為其能得的支付費用

每個實驗向其對應的器材連邊，容量為inf

每個器材向超源連邊，容量為其費用

在最小割求出後在建立一次層次圖

有層次的就是選擇的實驗與儀器

(卡死在輸入系列+_+)

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int inf=1e9;
const int maxn=500;
int n,m,s=0,t;
struct node{int v,f,nxt;}E[maxn*200];
int head[maxn],tot=1;
int lev[maxn],sum,maxf;

void add(int u,int v,int f)
{
    E[++tot].nxt=head[u];
    E[tot].v=v; E[tot].f=f;
    head[u]=tot;
}

int bfs()
{
    memset(lev,-1,sizeof(lev)); lev[s]=0;
    queue<int> q; q.push(s);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v=E[i].v;
            if(lev[v]==-1&&E[i].f)
            {
                lev[v]=lev[u]+1;
                if(v==t) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

int dfs(int u,int cap)
{
    if(u==t) return cap;
    int flow=cap;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v=E[i].v;
        if(lev[v]==lev[u]+1&&E[i].f&&flow)
        {
            int f=dfs(v,min(E[i].f,flow));
            flow-=f;
            E[i].f-=f; E[i^1].f+=f; 
        }
    }
    return cap-flow;
}

int main()
{
    n=read();m=read();t=n+m+1;
    for(int i=1;i<=n;++i)
    {
    	int k=read(); sum+=k;
    	add(s,i,k); add(i,s,0);
    	
    	char ss=getchar();
        while(ss!='\n'&&ss!='\r')//這個輸入自行體會
        {
            int x=0;
            while(ss>='0'&&ss<='9') x=x*10+ss-'0',ss=getchar();
            if(x) add(i,x+n,inf),add(x+n,i,0);
            if(ss!='\n'&&ss!='\r') ss=getchar();
        }
    } 
    for(int i=1;i<=m;++i)
    add(i+n,t,read()),add(t,i+n,0);
    
    while(bfs())
    maxf+=dfs(s,inf);
    
    bfs();
    for(int i=1;i<=n;++i)
    if(lev[i]!=-1) printf("%d ",i);
    printf("\n");
    
    for(int i=n+1;i<=n+m;++i)
    if(lev[i]!=-1) printf("%d ",i-n);
    printf("\n%d",sum-maxf);
    return 0;
}
           

領三倍經驗

洛谷P4174 [NOI2006]最大獲利

洛谷P3410 拍照