盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5294 Tricks Device(网络流 最短路)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5294

题意

有一张图,其中n个点,m条双向边,边有权值。所以从起点1走到终点n有一个最短时间。问:
(1)最少去掉多少条边,使得从起点到终点的时间大于最短时间(走不到也算)
(2)最多去掉多少条边,使得从起点到终点的时间仍然为最短时间。
其中 n ≤ 2000; m ≤ 60000

思路

spfa时找到最少边数的最短路,总边数减去最少变数即为第二问答案。
第一问中,根据在最短路的边构造边流量为1的新图,对新图求最大流即为第一问答案。

比赛的时候思路非常清晰,但是看到n和m这么大,感觉网络流肯定T,然后就没有敲。。。实际上新图的规模很小

代码

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
const int INF = (1 << 30);
using namespace std;
const int N = 2010;
const int M = 60010;
vector< pair<int, int> > G[N];
int n, m;
const int maxn = 2010;
const int maxm = 60010;
struct node {
int v; // vertex
int cap; // capacity
int flow; // current flow in this arc
int nxt;
} e[maxm * 2];
int g[maxn], cnt;
int st, ed;
int dd[maxn], cc[maxn];
queue<int> Q;
void spfa(int st, int ed) {
dd[st] = cc[st] = 0;
bool in[maxn] = {0};
while(!Q.empty()) Q.pop();
in[st] = true;
Q.push(st);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
in[u] = false;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first, c = G[u][i].second;
if (dd[u] + c == dd[v]) cc[v] = min(cc[v], cc[u] + 1);
if (dd[u] + c < dd[v]) {
cc[v] = cc[u] + 1;
dd[v] = dd[u] + c;
if (!in[v]) Q.push(v), in[v] = true;
}
}
}
}
void add(int u, int v, int c) {
e[++cnt].v = v;
e[cnt].cap = c;
e[cnt].flow = 0;
e[cnt].nxt = g[u];
g[u] = cnt;
e[++cnt].v = u;
e[cnt].cap = 0;
e[cnt].flow = 0;
e[cnt].nxt = g[v];
g[v] = cnt;
}
void init() {
memset(g, 0, sizeof(g));
cnt = 1;
st = 1, ed = n;
for (int u = 1; u <= n; u++) {
for (int i = 0; i < G[u].size(); i++) {
if (dd[u] + G[u][i].second == dd[G[u][i].first]) add(u, G[u][i].first, 1);
}
}
}
int dist[maxn], numbs[maxn], q[maxn];
void rev_bfs() {
int font = 0, rear = 1;
for (int i = 0; i <= n; i++) { //n为总点数
dist[i] = maxn;
numbs[i] = 0;
}
q[font] = ed;
dist[ed] = 0;
numbs[0] = 1;
while(font != rear) {
int u = q[font++];
for (int i = g[u]; i; i = e[i].nxt) {
if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue;
dist[e[i].v] = dist[u] + 1;
++numbs[dist[e[i].v]];
q[rear++] = e[i].v;
}
}
}
int maxflow() {
n += 3;
rev_bfs();
int u, totalflow = 0;
int curg[maxn], revpath[maxn];
for(int i = 0; i <= n; ++i) curg[i] = g[i];
u = st;
while(dist[st] < n) {
if(u == ed) { // find an augmenting path
int augflow = INF;
for(int i = st; i != ed; i = e[curg[i]].v)
augflow = min(augflow, e[curg[i]].cap);
for(int i = st; i != ed; i = e[curg[i]].v) {
e[curg[i]].cap -= augflow;
e[curg[i] ^ 1].cap += augflow;
e[curg[i]].flow += augflow;
e[curg[i] ^ 1].flow -= augflow;
}
totalflow += augflow;
u = st;
}
int i;
for(i = curg[u]; i; i = e[i].nxt)
if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
if(i) { // find an admissible arc, then Advance
curg[u] = i;
revpath[e[i].v] = i ^ 1;
u = e[i].v;
} else { // no admissible arc, then relabel this vertex
if(0 == (--numbs[dist[u]])) break; // GAP cut, Important!
curg[u] = g[u];
int mindist = n;
for(int j = g[u]; j; j = e[j].nxt)
if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != st)
u = e[revpath[u]].v; // Backtrack
}
}
n -= 3;
return totalflow;
}
int main () {
while(~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; i++) {
G[i].clear();
dd[i] = cc[i] = INF;
}
int u, v, l;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &l);
G[u].push_back({v, l});
G[v].push_back({u, l});
}
spfa(1, n);
init();
printf("%d %d\n", maxflow(), m - cc[n]);
}
return 0;
}

更新日志

  • 14108329 2015-07-22 14:29:43 Accepted 5294 93MS 4992K 3960 B C++ SIO__Five