无力吐槽递归的效率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;
}