- 技术博客
- [HNOI2001]软件开发
最小费用最大流
(仅提供本人建图思路过程）
首先拆点，分为早上和晚上两个点，i和n+i。
1.从n+i向T连流量为w[i]，费用为0的边。（表示每天必须要拥有w[i]块可以用的毛巾，不管用什么方法）
我们知道对于一天的需要的毛巾，可以有两种方法来集齐：直接买新毛巾；或是经过清洗。
2.如果是买新毛巾，那么：从S向n+i连流量为w[i]，费用为f的边。
3.如果是经过清洗，那么：从i向n+i+a+1连流量为w[i]，费用为fa的边；从i向n+i+b+1连流量为w[i]，费用为fb的边。（表示最多有w[i]块毛巾，可以经清洗，a天后或b天后使用）
4.很明显，我们需要把S和i连起来：从S向i连流量为w[i]，费用为0的边。
好像就这样建完了。然后只有20分。
然后我们发现一个这样的问题：如果之前某一天用完了好多毛巾，经清洗后，在i+a+1天清洗完成并用了，结果还剩余一些，那么这些毛巾，不就可以给i+a+1+1天继续用吗？
5.从n+i向n+i+1连流量为inf，费用为0的边。（注意这里的流量为inf，因为我们是不知道有多少毛巾的）
#include <bits/stdc++.h>
#define int long long
using namespace std
;
const int N
=1e3+5,inf
=2e9;
int n
,a
,b
,f
,fa
,fb
,w
,s
,t
,mincost
;
int d
[N
*2];
bool vis
[N
*2],ff
[N
*2];
int cnt
=1,head
[N
*2];
struct edge
{int next
,to
,w
,dis
;}e
[N
*12];
inline void add(int u
,int v
,int w
,int dis
)
{
cnt
++;
e
[cnt
].next
=head
[u
];
e
[cnt
].to
=v
;
e
[cnt
].w
=w
;;
e
[cnt
].dis
=dis
;
head
[u
]=cnt
;
}
inline void insert(int u
,int v
,int w
,int dis
)
{
add(u
,v
,w
,dis
); add(v
,u
,0,-dis
);
}
queue
<int>q
;
inline bool spfa()
{
memset(d
,60,sizeof(d
));
int maxn
=d
[0];
memset(vis
,false,sizeof(vis
));
d
[s
]=0; vis
[s
]=true; q
.push(s
);
while (q
.size())
{
int u
=q
.front(); q
.pop();
vis
[u
]=false;
for (register int i
=head
[u
]; i
; i
=e
[i
].next
)
if (e
[i
].w
&& d
[e
[i
].to
]>d
[u
]+e
[i
].dis
)
{
d
[e
[i
].to
]=d
[u
]+e
[i
].dis
;
if (!vis
[e
[i
].to
]) q
.push(e
[i
].to
),vis
[e
[i
].to
]=true;
}
}
if (d
[t
]!=maxn
) return true;
return false;
}
int dfs(int u
,int flow
)
{
if (u
==t
) return flow
;
int last
=flow
;
ff
[u
]=true;
for (register int i
=head
[u
]; i
; i
=e
[i
].next
)
if (!ff
[e
[i
].to
] && e
[i
].w
&& d
[e
[i
].to
]==d
[u
]+e
[i
].dis
)
{
int k
=dfs(e
[i
].to
,min(e
[i
].w
,last
));
if (!k
) {d
[e
[i
].to
]=-1; continue;}
e
[i
].w
-=k
; e
[i
^1].w
+=k
;
mincost
+=e
[i
].dis
*k
;
last
-=k
;
if (!last
) break;
}
return flow
-last
;
}
inline void dinic()
{
while (spfa())
{
memset(ff
,false,sizeof(ff
));
dfs(s
,inf
);
}
}
signed main(){
scanf("%lld%lld%lld%lld%lld%lld",&n
,&a
,&b
,&f
,&fa
,&fb
);
s
=0; t
=2*n
+1;
for (register int i
=1; i
<=n
; ++i
)
{
scanf("%lld",&w
);
insert(n
+i
,t
,w
,0);
insert(s
,n
+i
,w
,f
);
insert(s
,i
,w
,0);
if (i
+a
+1<=n
) insert(i
,n
+i
+a
+1,inf
,fa
);
if (i
+b
+1<=n
) insert(i
,n
+i
+b
+1,inf
,fb
);
if (i
<n
) insert(i
,i
+1,inf
,0);
}
dinic();
printf("%lld\n",mincost
);
return 0;
}
