题目
题解
由于题目中给的限制（每一条边只能走一次），采用SPFA跑从1到n再跑从n到1的最短距离，最后建网络流跑最大流的方法。这样就需要在建边时建双向边，但跑SPFA时需要特判这条边是正向边还是反向边。由于只要满足时间最短，就一定有 dis1[u] + edge[i].w + dis2[v] == ans （即图中至少有一条边，设其两端为u，v，满足该边的边权+左端点u到1的时间花费+右端点v到n的时间花费=最短时间），那么如果要跑最短路，这条边很有可能是可以经过的。所以将该边的网络流边权设置为1。网络流的建图就这样，再跑一遍网络流就可以了。
代码
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define oo 0x3fffffff
using namespace std;
const int N =
100010;
const int M =
350;
struct Edge {
int u, v, w, f, next;
} edge[
5 * N];
int n, m, ans, dis[M],
queue[
5 * N], head[
5 * N], num =
1;
long long dis1[M], dis2[M];
bool vis[M];
void add(
int u,
int v,
int w) {
num ++;
edge[num].u = u;
edge[num].v = v;
edge[num].w = w;
edge[num].f =
0;
edge[num].next = head[u];
head[u] = num;
}
stack <int> q1;
void spfa1() {
memset(dis1,
127,
sizeof(dis1));
memset(vis,
0,
sizeof(vis));
vis[
1] =
true; dis1[
1] =
0; q1.push(
1);
while(! q1.empty()) {
int u = q1.top();
q1.pop();
vis[u] =
false;
for(
int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if((i &
1) ==
0 && dis1[v] > dis1[u] + edge[i].w) {
dis1[v] = dis1[u] + edge[i].w;
if(! vis[v]) {
vis[v] =
true;
q1.push(v);
}
}
}
}
}
stack <int> q2;
void spfa2() {
memset(dis2,
127,
sizeof(dis2));
memset(vis,
0,
sizeof(vis));
vis[n] =
true; dis2[n] =
0; q2.push(n);
while(! q2.empty()) {
int u = q2.top();
q2.pop();
vis[u] =
false;
for(
int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if((i &
1) ==
1 && dis2[v] > dis2[u] + edge[i].w) {
dis2[v] = dis2[u] + edge[i].w;
if(! vis[v]) {
vis[v] =
true;
q2.push(v);
}
}
}
}
}
void zero() {
memset(vis,
0,
sizeof(vis));
memset(dis,
0,
sizeof(dis));
memset(
queue,
0,
sizeof(
queue));
}
bool bfs() {
int h =
0, tail =
1;
vis[
1] =
1; dis[
1] =
0;
queue[
1] =
1;
while(h < tail) {
int u =
queue[++ h];
for(
int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if(! vis[v] && edge[i].f) {
vis[v] =
1;
queue[++ tail] = v;
dis[v] = dis[u] +
1;
}
}
}
if(vis[n])
return true;
return false;
}
int dfs(
int u,
int delta) {
if(u == n || ! delta)
return delta;
int ans =
0;
for(
int i = head[u]; i && delta; i = edge[i].next) {
int v = edge[i].v;
if(dis[v] == dis[u] +
1 && edge[i].f) {
int dd = dfs(v, min(delta, edge[i].f));
edge[i].f -= dd;
edge[i ^
1].f += dd;
delta -= dd;
ans += dd;
}
}
if(! ans) dis[u] = -
1;
return ans;
}
int Maxflow() {
int ans =
0;
while(
1) {
zero();
if(! bfs())
break;
ans += dfs(
1, oo);
}
return ans;
}
int main() {
freopen(
"change.in",
"r", stdin);
freopen(
"change.out",
"w", stdout);
scanf(
"%d %d", &n, &m);
for(
int i =
1; i <= m; i ++) {
int u, v, w;
scanf(
"%d %d %d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
spfa1();
spfa2();
ans = dis1[n];
for(
int i =
2; i <= num; i +=
2) {
int u = edge[i].u, v = edge[i].v;
if(dis1[u] + edge[i].w + dis2[v] == ans){
edge[i].f =
1;
}
}
printf(
"%d", Maxflow());
return 0;
}
