NOI2006最大获益

Posted on By 二价氢

无力吐槽递归的效率233333

对比:

下面是递归的具体耗时:

接着是非递归的具体耗时

(评测参数为g++ -o profit.exe profit.cpp -O2

好了,下面是具体模型(网络流讲做法无意义!)

例:

有\(M\)个项目和\(N\)个员工。做项目\(i\)可以获得\(A_i\)元,但是必须雇用若干个指定的员工。雇用员工\(j\)需要花费\(B_j\)元,且一旦雇用,员工\(j\)可以参加多个项目的开发。问经过合理的项目取舍,最多能挣多少钱。\((1 \le M, N \le 100)\)

这种模型称为“蕴含式最大获利问题”,应套用最大权闭合子图的建模方法解决,参见:【POJ 2987 Firing】 最大权闭合子图

下面是AC-Code

注意被注释掉的两个函数,它们是递归式的Dinic,这里需要采用非递归的Dinic以防超时(原因见上面啊QwQ)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=55010,maxm=(50010*3+5010)*2;
const int s=0,delta=5000,inf=255;
struct edge{int s,t,v,o,n;}e[maxm];
int head[maxn],cur[maxn],path[maxn],path_n,te;
int n,m,t;
int p[5005],sigmap;
int lay[maxn];
void ae(int s,int t,int v)
{
    int e1,e2;
    e1=te++;e2=te++;
    e[e1].s=s;e[e1].t=t;e[e1].v=v;e[e1].n=head[s];e[e1].o=e2;head[s]=e1;
    e[e2].s=t;e[e2].t=s;e[e2].v=0;e[e2].n=head[t];e[e2].o=e1;head[t]=e2;
}
bool build()
{
    int u;
    memset(lay,-1,sizeof(lay));
    queue <int>Q;
    Q.push(s);lay[s]=0;
    while (!Q.empty())
    {
        u=Q.front();Q.pop();
        for (int c=head[u];~c;c=e[c].n)
            if (e[c].v&&lay[e[c].t]==-1)
            {
                lay[e[c].t]=lay[u]+1;
                Q.push(e[c].t);
            }
    }
    return lay[t]!=-1;
}
/*
int find(int u,int low)
{
    if (u==t)
        return low;
    int ans=0,tans;
    for (int c=head[u];(~c)&&low;c=e[c].n)
        if (lay[e[c].t]==lay[u]+1&&(tans=find(e[c].t,min(low,e[c].v))))
        {
            e[c].v-=tans;
            e[c^1].v+=tans;
            ans+=tans;
            low-=tans;
        }
    return ans;
}
int dinic()
{
    int ans=0,tans;
    while (build())
        while (tans=find(0,inf))
            ans+=tans;
    return ans;
}*/
int dinic()
{
    int ret=0;
    while (build())
    {
        int path_n=0;
        int x=s;
        memcpy(cur,head,sizeof(cur));
        while (1)
        {
            if (x==t)
            {
                int mink=-1,delta=inf;
                for (int i=0;i<path_n;i++)
                {
                    if (e[path[i]].v<delta)
                    {
                        delta=e[path[i]].v;
                        mink=i;
                    }
                }
                for (int i=0;i<path_n;i++)
                {
                    e[path[i]].v-=delta;
                    e[path[i]^1].v+=delta;
                }
                ret+=delta;
                path_n=mink;
                x=e[path[path_n]].s;
            }
            int ep;
            for (ep=cur[x];~ep;ep=e[ep].n)
            {
                if (e[ep].v)
                {
                    int y=e[ep].t;
                    if (lay[y]==lay[x]+1)
                        break;
                }
            }
            cur[x]=ep;
            if (~ep)
            {
                path[path_n++]=ep;
                x=e[ep].t;
            }else
            {
                if (!path_n)
                    break;
                lay[x]=-1;
                --path_n;
                x=e[path[path_n]].s;
            }
        }
    }
    return ret;
}
int main()
{
    //freopen("profit.in","r",stdin);
    //freopen("profit.out","w",stdout);
    int i,ans=0;
    int a,b,c;
    scanf("%d%d",&n,&m);
    t=m+n+1;
    memset(head,-1,sizeof(head));
    for (i=1;i<=n;i++)
    {
        scanf("%d",&c);
        ae(i+m,t,c);
    }
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        ae(i,a+m,inf);
        ae(i,b+m,inf);
        ae(s,i,c);
        ans+=c;
    }
    printf("%d\n",ans-dinic());
    return 0;
}

AC通道