首页 > 代码库 > 【BZOJ1061】【NOI2008】志愿者招募 费用流神题、单纯形裸题（代码费用流）
【BZOJ1061】【NOI2008】志愿者招募 费用流神题、单纯形裸题（代码费用流）
题目模型出的真心神。
需要好难才能推出来。
本来打算写一篇好的题解，但是状态实在不好，没弄会这道题。
只能先扒建边留个坑了。
据说“单纯形算法”可以高速+裸建图 水过此题（呃，或曰此题乃单纯形裸题是也。）
留坑前先给个链接吧，应该是目前网上最好的此题题解：
BYV大神的题解：www.byvoid.com/blog/noi-2008-employee/#more-916
我的代码：
<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1050
#define M 30100
#define P 105
#define inf 0x3f3f3f3f
using namespace std;
struct KSD
{
int u,v,len,fee,next;
}e[M];
int head[N],cnt;
void add(int u,int v,int len,int fee)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].len=len;
e[cnt].fee=fee;
e[cnt].next=head[u];
head[u]=cnt;
}
int s,t,dist[N];
int pre[N],lim[N];
bool in[N];
queue<int>q;
void spfa()
{
memset(dist,0x3f,sizeof(dist));
memset(lim,0,sizeof(lim));
while(!q.empty())q.pop();
int i,u,v;
dist[s]=0,in[s]=1;
lim[s]=inf;
q.push(s);
while(!q.empty())
{
u=q.front(),q.pop(),in[u]=0;
for(i=head[u];i;i=e[i].next)
{
v=e[i].v;
if(!e[i].len)continue;
if(dist[v]>dist[u]+e[i].fee)
{
dist[v]=dist[u]+e[i].fee;
lim[v]=min(e[i].len,lim[u]);
pre[v]=i;
if(!in[v])
{
in[v]=1;
q.push(v);
}
}
}
}
return ;
}
void handle(int flow)
{
for(int i=pre[t];i;i=pre[e[i].u])
{
e[i].len-=flow;
e[i^1].len+=flow;
}
}
int n,m,minfee;
int need[N];
int main()
{
// freopen("test.in","r",stdin);
int i,a,b,c;
scanf("%d%d",&n,&m),n++;
s=n+1,t=n+2,cnt=1;
for(i=1;i<n;i++)scanf("%d",&need[i]);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b+1,inf,c),add(b+1,a,0,-c);
}
for(i=1;i<=n;i++)
{
c=need[i]-need[i-1];
if(c>=0)add(s,i,c,0),add(i,s,0,0);
else add(i,t,-c,0),add(t,i,0,0);
if(i>1)add(i,i-1,inf,0),add(i-1,i,0,0);
}
while(spfa(),dist[t]<inf)
{
minfee+=dist[t]*lim[t];
handle(lim[t]);
}
printf("%d\n",minfee);
return 0;
}
</span>【BZOJ1061】【NOI2008】志愿者招募 费用流神题、单纯形裸题（代码费用流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。