stdKonjac's Blog

 要做到不可替代,就要与众不同。

【Snow】

【问题描述】

有一天,YJQ要去登门造访ZZY家。ZZY的大门外有n个站台,用1到n的正整数编号,YJQ需要对每个站台访问恰好一定次数以后才能到YYY家。站台之间有m个单向的传送门,通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门,YJQ就需要乘坐公共汽车,并花费1毛钱。值得庆幸的是,任意两个站台之间都有公共汽车直达。

现在给定每个站台必须访问的次数,对于站台i,YJQ必须恰好访问Fi次(不能超过)。

我们用u,v,w三个参数描述一个传送门,表示从站台u到站台v有一个最多可以使用w次的传送门(不一定要使用w次)。对于任意一对传送门(u1,v1)和(u2,v2),如果有u1<u2,则有v1≤v2;如果有v1<v2,则有u1≤u2,且u1=u2和v1=v2不同时成立。

YJQ可以从任意的站台开始,从任意的站台结束。出发去开始的站台需要花费1毛钱。现在请帮助抠门的YJQ求出打开大门需要最少花费多少毛钱。

【输入格式】

第一行包含两个正整数n,m,意义见题目描述。

第二行包含n个正整数,第i个数表示Fi。

接下来有m行,每行有三个正整数u,v,w表示从u到v有一个可以使用w次的传送门。

【输出格式】

仅一行包含一个整数表示答案。

【输入样例】

4 3

5 5 5 5

1 2 1

3 2 1

3 4 1

【输出样例】

17

【数据范围】

100%的数据满足1≤n≤10000,1≤m≤100000

对于所有的u,v满足1≤u,v≤n,u≠v;对于所有的w,Fi,满足1≤w,Fi≤50000.

要想花费最少,那么显然要最大效率的利用传送门。

于是可以考虑用网络流中的最大流来解决这个问题。

考虑将限制条件作为边的流量,即把一个点拆成两个点,其中一个与S连一条流量为F[i]的边,另一条与T连一条流量为F[i]的边。

对于传送门间的两个点u,v将u1和v2连一条流量为w(u,v)的边,之后跑最大流即可。

答案显然是∑F[i]-Maxflow。

本题的要点就是通过”最大效率的利用传送门“想到网络流来做。

实际上,也可以用DP或者有上下界的最小费用流来做,不过最大流最简洁易懂。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.