货物运输题解

这道题是我来郑州集训以来终于AC的第一道题。我真的非常弱啊!

题目在HUD的oj上面也有,我方便大家提交,也放在了洛谷上。HUD链接:HDU3667 Transportation 洛谷链接: 洛谷U19917 货物运输

题目要求我也顺便说一下:

某国有$N$座城市,由$M$条单向道路相连。 你希望从城市1将k个单位的货物运送到城市$N$。 道路很不安全,如果一次携带$x$个单位的货物,需要花费$a_i * x^2$的费用,每条道路还有容量限制。 货物必须以整数为单位携带。 求最小花费。

输入格式:

输入包含多组数据。 每组数据的第一行包含3个整数$N$、$M$、$K$。 接下来$M$行,每行4个整数$u_i$、$v_i$、$a_i$、$c_i$,表示有一条从城市$u_i$到城市$v_i$的单向道路,危险系数为$a_i$,容量为$c_i$。

输出格式:

对于每组数据,输出一行一个整数,表示最小花费。如果不可能运输全部K单位的货物,输出-1。

说明:

对于10%的数据,$N,M ≤ 5$。 对于100%的数据,$1 ≤ N ≤ 100$,$1 ≤ M ≤ 5000$,$0 ≤ K ≤ 100$,$1 ≤ u_i , v_i ≤ N$,$0 < a_i ≤ 100$,$ci ≤ 5$,数据组数$≤ 5$。


等等这不是最小费用最大流么,简单啊,从源点连个k容量的边到起点,跑一遍spfa的dinic板子不就可以了?

要是这么想,哦,那你naive了,认真读题,题目的费用可不是常规线性的,而是一个二次递增的。

那么怎么办呢,别急先看一眼数据范围,k最多只有100,那么,我们在寻找增广路的时候,不能一次让这条路满流,而是每次让它增加1,同时,每增加1,这条路的费用就会改变,那么,每次增加流时,顺便更新一下这条增广路的费用不就好了?

那么,每次增加多少费用呢?看这个式子 $a_i*x^2$ 。每增加1,那么这个式子就变成了$x^2$就会增加$x^2-(x-1)^2$,显然通过这个式子,发现每条边的费用是$2*x*a_i$的,每次增加的流量$x=1$,那么这个式子就是$a,3a,5a…$ 递增的,这样我们只要记录初始费用和当前费用,每跑一次增广路,就让正向边$+2a$,反向边$-2a$。

但是,这么做,会WA,因为我们忽略了一个小细节,那就是,反向边是留给之前一步的反悔操作,因为费用在增长,所以,反向边的增长速度必须要比正向边慢一步,才能保证在反悔时值还是前一步的值,所以,在初始赋值时,以往费用边是 $ -a $ ,现在也赋值成 $ a $,在减 $ 2a $ 时候就正好错开了一步了!

接下来,按照这个操作跑费用流就可以了,当最大流小于 $ k $ 时候输出-1,否则输出费用。

大家最想要的代码来了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
#define OI//在线测评注释掉
//#define KCP
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> Pair;

const int maxn=110;
const int inf=0x7f7f7f7f;
const LL linf=0x7f7f7f7f7f7f7f;

typedef struct Edge_Node
{
trueEdge_Node *next,*turn;
trueint to,flow,now_cost,init_cost;//当前费用,原来费用
}EdgeNode,*Edge;

EdgeNode e[10010];
Edge head[maxn],cur[maxn];
int n,m,k,s,t,size;
int dist[maxn],nxt[maxn];
bool vis[maxn];

inline void add(int u,int v,int flow,int cost)
{
trueEdge node1=e+size++,node2=e+size++;
truenode1->next=head[u],node2->next=head[v];
truenode1->to=v,node2->to=u;
truenode1->now_cost=cost,node2->now_cost=cost;//注意是正的,不是负的
truenode1->init_cost=cost,node2->init_cost=cost;
truenode1->flow=flow,node2->flow=0;
truenode1->turn=node2,node2->turn=node1;
truehead[u]=node1,head[v]=node2;
}

bool spfa()//spfa都会的
{
truememset(vis,0,sizeof(vis));
truememset(dist,0x7f,sizeof(dist));
truequeue<int> que;
trueque.push(s);
truedist[s]=0,vis[s]=1;
truewhile(!que.empty())
true{
truetrueint u=que.front();
truetrueque.pop();
truetruevis[u]=0;
truetruefor(Edge node=head[u];node!=NULL;node=node->next)
truetrue{
truetruetrueint v=node->to;
truetruetrueif(node->flow && dist[v]>dist[u]+node->now_cost)
truetruetrue{
truetruetruetruedist[v]=dist[u]+node->now_cost;
truetruetruetruecur[v]=node;//路径记录
truetruetruetruenxt[v]=u;
truetruetruetrueif(!vis[v])
truetruetruetrue{
truetruetruetruetruevis[v]=1;
truetruetruetruetrueque.push(v);
truetruetruetrue}
truetruetrue}
truetrue}
truetrue
true}
truereturn dist[t]<inf;
}

Pair Flow_Cost()
{
trueint flow=0,cost=0;
truewhile(spfa())
true{
truetruefor(int pos=t;pos!=s;pos=nxt[pos])
truetrue{
truetruetrueEdge node=cur[pos];
truetrue node->now_cost+=node->init_cost*2;//当前费用增加2a
truetrue node->turn->now_cost-=node->turn->init_cost*2;
truetrue node->flow--;
truetruetruenode->turn->flow++;
truetrue}
truetrueflow++;//流量每次增加1
truetruecost+=dist[t];
true}
truereturn make_pair(flow,cost);
}

int main()
{
true#ifdef OI
truefreopen("transportation.in","r",stdin);
truefreopen("transportation.out","w",stdout);
true#endif
truewhile(scanf("%d%d%d",&n,&m,&k)!=EOF)
true{
truetruesize=0;//注意多测初始化
truetruememset(head,0,sizeof head);
truetrues=0,t=n+1;
truetrueadd(s,1,k,0);//总容量限制k
truetrueadd(n,t,k,0);
truetruefor(int i=1;i<=m;i++)
truetrue{
truetruetrueint u,v,f,a;
truetruetruescanf("%d%d%d%d",&u,&v,&a,&f);
truetruetrueadd(u,v,f,a);
truetrue}
truetruePair ans=Flow_Cost();
truetrueif(ans.first<k)
truetruetrueputs("-1");
truetrueelse
truetruetrueprintf("%d\n",ans.second);
true}
true#ifdef KCP//卡测评,忽略我的恶意
truewhile(1);
true#endif
truereturn 0;
}

那么,就这样吧,有兴趣的同学实现一下,还有一种拆点做法,有能力可以尝试哦!