【费用流】BZOJ1061[NOI2008]-志愿者招募
【题目大意】
一个项目需要n天完成,其中第i天至少需要Ai个人。共有m类人可以招募,其中第i类可以从第Si天做到第Ti天,每人的招募费用为Ci元。求最小招募费用。
【思路】
byvoid神犇的建图详解,对理解网络流有很好的帮助,下面再引用一下,原po请戳:★
这道题正确的解法是构造网络,求网络最小费用最大流,但是模型隐藏得较深,不易想到。构造网络是该题的关键,以下面一个例子说明构图的方法和解释。
例如一共需要4天,四天需要的人数依次是4,2,5,3。有5类志愿者,如下表所示:
种类 1 2 3 4 5 时间 1-2 1-1 2-3 3-3 3-4 费用 3 4 3 5 6 设雇佣第i类志愿者的人数为X[i],每个志愿者的费用为V[i],第j天雇佣的人数为P[j],则每天的雇佣人数应满足一个不等式,如上表所述,可以列出
P[1] = X[1] + X[2] >= 4
P[2] = X[1] + X[3] >= 2
P[3] = X[3] + X[4] +X[5] >= 5
P[4] = X[5] >= 3
对于第i个不等式,添加辅助变量Y[i] (Y[i]>=0) ,可以使其变为等式
P[1] = X[1] + X[2] - Y[1] = 4
P[2] = X[1] + X[3] - Y[2] = 2
P[3] = X[3] + X[4] +X[5] - Y[3] = 5
P[4] = X[5] - Y[4] = 3
在上述四个等式上下添加P[0]=0,P[5]=0,每次用下边的式子减去上边的式子,得出
① P[1] - P[0] = X[1] + X[2] - Y[1] = 4
② P[2] - P[1] = X[3] - X[2] -Y[2] +Y[1] = -2
③ P[3] - P[2] = X[4] + X[5] - X[1] - Y[3] + Y[2] =3
④ P[4] - P[3] = - X[3] - X[4] + Y[3] - Y[4] = -2
⑤ P[5] - P[4] = - X[5] + Y[4] = -3
观察发现,每个变量都在两个式子中出现了,而且一次为正,一次为负。所有等式右边和为0。接下来,根据上面五个等式构图。
- 每个等式为图中一个顶点,添加源点S和汇点T。
- 如果一个等式右边为非负整数c,从源点S向该等式对应的顶点连接一条容量为c,权值为0的有向边;如果一个等式右边为负整数c,从该等式对应的顶点向汇点T连接一条容量为c,权值为0的有向边。
- 如果一个变量X[i]在第j个等式中出现为X[i],在第k个等式中出现为-X[i],从顶点j向顶点k连接一条容量为∞,权值为V[i]的有向边。
- 如果一个变量Y[i]在第j个等式中出现为Y[i],在第k个等式中出现为-Y[i],从顶点j向顶点k连接一条容量为∞,权值为0的有向边。
构图以后,求从源点S到汇点T的最小费用最大流,费用值就是结果。
根据上面的例子可以构造出如下网络,红色的边为每个变量X代表的边,蓝色的边为每个变量Y代表的边,边的容量和权值标已经标出(蓝色没有标记,因为都是容量∞,权值0)。
在这个图中求最小费用最大流,流量网络如下图,每个红色边的流量就是对应的变量X的值。
所以,答案为43+23+3*6=36。
上面的方法很神奇得求出了结果,思考为什么这样构图。我们将最后的五个等式进一步变形,得出以下结果
① - X[1] - X[2] + Y[1] + 4 = 0
② - X[3] + X[2] + Y[2] - Y[1] - 2 = 0
③ - X[4] - X[5] + X[1] + Y[3] - Y[2] + 3 = 0
④ X[3] + X[4] - Y[3] + Y[4] - 2 = 0
⑤ X[5] - Y[4] - 3 = 0
可以发现,每个等式左边都是几个变量和一个常数相加减,右边都为0,恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量,负的变量相当于流出该顶点的流量,而正常数可以看作来自附加源点的流量,负的常数是流向附加汇点的流量。因此可以据此构造网络,求出从附加源到附加汇的网络最大流,即可满足所有等式。而我们还要求最小,所以要在X变量相对应的边上加上权值,然后求最小费用最大流。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define S 0
#define T n+2
using namespace std;
struct node
{
int to,pos,cap,val;
};
const int MAXM=+;
const int MAXN=+;
const int INF=0x7fffffff;
int n,m,a[MAXN],s[MAXM],t[MAXM],c[MAXM];
int pre[MAXN],preedge[MAXN];
vector<node> E[MAXN]; void addedge(int u,int v,int ca,int va)
{
E[u].push_back((node){v,E[v].size(),ca,va});
E[v].push_back((node){u,E[u].size()-,,-va});
} int SPFA()
{
queue<int> que;
int vis[MAXN],dis[MAXN];
memset(vis,,sizeof(vis));
memset(pre,-,sizeof(pre));
for (int i=S;i<=T;i++) dis[i]=INF;
que.push();
vis[]=;
dis[]=;
while (!que.empty())
{
int head=que.front();que.pop();
vis[head]=;
for (int i=;i<E[head].size();i++)
{
node &tmp=E[head][i];
if (tmp.cap> && dis[tmp.to]>dis[head]+tmp.val)
{
dis[tmp.to]=dis[head]+tmp.val;
pre[tmp.to]=head;
preedge[tmp.to]=i;
if (!vis[tmp.to])
{
que.push(tmp.to);
vis[tmp.to]=;
}
}
}
}
if (dis[T]==INF) return ;else return ;
} int mcf()
{
int flow=;
int ans=;
while (SPFA())
{
int f=INF;
for (int i=T;pre[i]!=-;i=pre[i])
{
node &tmp=E[pre[i]][preedge[i]];
f=min(f,tmp.cap);
}
for (int i=T;pre[i]!=-;i=pre[i])
{
node &tmp=E[pre[i]][preedge[i]];
tmp.cap-=f;
E[tmp.to][tmp.pos].cap+=f;
ans+=f*tmp.val;
}
}
return ans;
} void init()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=m;i++) scanf("%d%d%d",&s[i],&t[i],&c[i]);
} void build()
{
a[]=a[n+]=;
for (int i=;i<=n+;i++)
{
int c=a[i]-a[i-];
if (c>) addedge(S,i,c,);
if (c<) addedge(i,T,-c,);
}
for (int i=;i<=m;i++)
addedge(s[i],t[i]+,INF,c[i]);
for (int i=;i<=n;i++) addedge(i+,i,INF,);
} int main()
{
init();
build();
cout<<mcf()<<endl;
return ;
}
最新文章
- kettle系列-4.kettle定制化开发工具类
- (翻译)Angular.js为什么如此火呢?
- iOS权限管理思路
- infragistcs 又
- OpenJudge计算概论-排队游戏【这个用到了栈的思想】
- sql之表连接 筛选条件放在 连接外和放在连接里的区别
- Java Socket 异常 Connection reset
- (六)《Java编程思想》——初始化及类的加载顺序
- Hibernate防止SQL注入
- icon大小
- iOS中 学会如何对sqlite3 进行封装 (纯手工)
- C语言实现将日期、时间保存到文本文件中
- Hbase思维导图之架构
- python文档-基本API命令翻译及使用方法!
- 《Nginx - 指令》- Rewrite/If/Set
- 能改变this各种情况下的总结,还有没有总结到的,请留言!!
- IntellJ IDEA 对于 Spring Boot2.0.2 配置文件application.properties 配置
- android shareUID
- asp.net core 的用户注册功能——Identity上手
- cv1.0入门
热门文章
- Codeforces 931.D Peculiar apple-tree
- Spring学习--引用其他Bean , 内部Bean
- The NPF driver isn&#39;t running
- UVa11988 Broken Keyboard (a.k.a. Beiju Text)
- bzoj 2245 费用流
- JS组件入门
- RabbitMQ消息队列(五): 主题分发
- ggplot2绘制多图
- python清华大学镜像
- js面向对象编程(二)构造函数的继承(转载)