Path
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 598 Accepted Submission(s): 147
Problem Description
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl’s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can’t reach his girl’s house in the very beginning, the answer is obviously zero. And you don’t need to guarantee that there still exists a way from Jerry’s house to his girl’s after blocking some edges.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n lines, each line containing a integer, the answer.
Sample Input
1
3 4
1 2 1
2 3 1
1 3 2
1 3 3
Sample Output
3
Source 2019 Multi-University Training Contest 1
巨坑巨烦的一道题，下午交的时候是TLE， 回来补提发现错了两组数据。。。
找了半天的bug也找不出问题。。。最后把图改成了有向图居然过了。。。。 坑啊！！！！！
做法：
先做一遍dijkstra，得到dis数组
对于每一条边（u,v）（居然是有向的！！！ 再次泄愤！） 如果dis[v]-dis[u] == (u, v)说明这条路在最短路上
将所有最短路构建成一个新的图，用sap求最小割就能得到结果
代码量还是挺大的。。。。。
AC Code
/*
* Copyright (c) 2019 Ng Kimbing, HNU, All rights reserved. May not be used, modified, or copied without permission.
* @Author: Ng Kimbing, HNU.
* @LastModified:2019-07-22 T 14:05:52.878 +08:00
*/
package ACMProblems.Summer2019.HDU;
import static ACMProblems.ACMIO.*;
import java.util.*;
public class Main {
// 此处省略IO 代码 （nextInt()）
static class VertexNode {
private int id;
private long weight;
public VertexNode(int id, long weight) {
this.id = id;
this.weight = weight;
}
public int getId() {
return id;
}
public long getWeight() {
return weight;
}
}
static class Edge {
int from;
int to;
long weight;
public Edge(int from, int to, long weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
static class Graph {
private int vertexNum;
private ArrayList<VertexNode>[] lists;
private Edge[] edges;
private int index = 0;
public Graph(int vertexNum, int edgeNum) {
this.vertexNum = vertexNum;
lists = new ArrayList[vertexNum];
for (int i = 0; i < vertexNum; ++i)
lists[i] = new ArrayList<>();
edges = new Edge[edgeNum * 2];
}
/**
* Add one edges into the graph. The weight will be changed if the edges already exists.
*
* @param a Start
* @param b End
* @param weight The weight of the edges from a to b
*/
public void addEdge(int a, int b, long weight) {
assert a < vertexNum && b < vertexNum;
// 居然是有向图。。气死个人
lists[a].add(new VertexNode(b, weight));
// lists[b].add(new VertexNode(a, weight));
edges[index++] = new Edge(a, b, weight);
// edges[index++] = new Edge(b, a, weight);
}
private long[] dijkstra(int a, int b) {
assert a < vertexNum && b < vertexNum;
long[] dis = new long[vertexNum];
boolean[] visited = new boolean[vertexNum];
// The heap used to find the closest vertex.
PriorityQueue<VertexNode> q = new PriorityQueue<>(vertexNum, Comparator.comparingLong(VertexNode::getWeight));
//initialize
q.add(new VertexNode(a, 0));
Arrays.fill(dis, 0x3f3f3f3f3f3f3f3fL);
dis[a] = 0;
while (!q.isEmpty()) {
// Current vertex.
VertexNode v = q.poll();
int currID = v.getId();
//Mark as visited.
visited[currID] = true;
//for each neighbor
for (VertexNode dest : lists[currID]) {
//if there is a shorter path
if (!visited[dest.getId()] && dis[currID] + dest.getWeight() < dis[dest.getId()]) {
dis[dest.getId()] = dis[currID] + dest.getWeight();
q.add(new VertexNode(dest.getId(), dis[dest.getId()]));
}
}
}
return dis;
}
}
static int maxn = 10005;
static class Graph2 {
int tol = 0;
int[] head;
int[] gap;
long[] dep;
int[] cur;
int[] pre;
Edge[] edges;
Graph2(int vertexNum, int edgeNum) {
head = new int[vertexNum + 10];
gap = new int[vertexNum + 10];
dep = new long[vertexNum + 10];
cur = new int[vertexNum + 10];
pre = new int[vertexNum + 10];
edges = new Edge[edgeNum];
Arrays.fill(head, -1);
}
static class Edge {
int to, next;
long cap, flow;
Edge(int to, int next, long cap, long flow) {
this.to = to;
this.next = next;
this.cap = cap;
this.flow = flow;
}
}
/**
* @param rw = 0, 有向图！！！！！
*/
void addEdge(int u, int v, long w, long rw) {
edges[tol] = new Edge(v, head[u], w, 0);
head[u] = tol++;
edges[tol] = new Edge(u, head[v], rw, 0);
head[v] = tol++;
}
long sap(int start, int end, int N) {
System.arraycopy(head, 0, cur, 0, head.length);
final long INF = 0x3f3f3f3f3f3f3f3fL;
int u = start;
pre[u] = -1;
gap[0] = N;
long ans = 0;
while (dep[start] < N) {
if (u == end) {
long min = INF;
for (int i = pre[u]; i != -1; i = pre[edges[i ^ 1].to])
if (min > edges[i].cap - edges[i].flow)
min = edges[i].cap - edges[i].flow;
for (int i = pre[u]; i != -1; i = pre[edges[i ^ 1].to]) {
edges[i].flow += min;
edges[i ^ 1].flow -= min;
}
u = start;
ans += min;
continue;
}
boolean flag = false;
int v = 0;
for (int i = cur[u]; i != -1; i = edges[i].next) {
v = edges[i].to;
if (edges[i].cap - edges[i].flow != 0 && dep[v] + 1 == dep[u]) {
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if (flag) {
u = v;
continue;
}
int min = N;
for (int i = head[u]; i != -1; i = edges[i].next)
if (edges[i].cap - edges[i].flow != 0 && dep[edges[i].to] < min) {
min = (int) dep[edges[i].to];
cur[u] = i;
}
gap[(int) dep[u]]--;
if (gap[(int) dep[u]] == 0)
return ans;
dep[u] = min + 1;
gap[(int) dep[u]]++;
if (u != start) u = edges[pre[u] ^ 1].to;
}
return ans;
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
// File f = new File("02");
// setStream(new FileInputStream(f));
int t = nextInt();
while (t-- != 0) {
int vertexNum = nextInt();
int edgeNum = nextInt();
Graph g = new Graph(vertexNum, edgeNum);//todo:
for (int i = 0; i < edgeNum; ++i) {
int a = nextInt() - 1;
int b = nextInt() - 1;
long weight = nextLong();
g.addEdge(a, b, weight);
}
long[] dis1 = g.dijkstra(0, g.vertexNum - 1);
Graph2 answerGraph = new Graph2(g.vertexNum, g.edges.length);
for (int i = 0; i < g.index; ++i) {
Edge edge = g.edges[i];
int start = edge.from;
int to = edge.to;
long foo = dis1[to] - dis1[start];
if (foo < 0) {
int temp = start;
start = to;
to = temp;
foo = -foo;
}
if (foo == edge.weight) {
answerGraph.addEdge(start, to, edge.weight, 0);
}
}
out.println(answerGraph.sap(0, g.vertexNum - 1, g.vertexNum));
}
out.flush();
}
}
标程（C++）：
#include <bits/stdc++.h>
template<class T>
bool Reduce(T &a, T const &b) {
return a > b ? a = b, true : false;
}
const int XN = 1e4 + 11;
const int INF = 2e9;
const long long oo = 1e18;
int n;
long long sp[XN];
namespace D {
struct Edge {
int to, v;
};
std::vector<Edge> G[XN];
void Run() {
static bool ud[XN];
std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int> >, std::greater<
> > Q;
std::fill(sp + 1, sp + 1 + n, oo);
std::fill(ud + 1, ud + 1 + n, 0);
sp[1] = 0;
Q.push(std::make_pair(0, 1));
while (!Q.empty()) {
int pos = Q.top().second;
Q.pop();
if (ud[pos])
continue;
ud[pos] = 1;
for (auto &e : G[pos]) {
int u = e.to;
if (Reduce(sp[u], sp[pos] + e.v))
Q.push(std::make_pair(sp[u], u));
}
}
}
}
namespace I {
struct Edge {
int to, cap, v;
Edge *rev, *pre;
} *G[XN], *preArc[XN];
void AddEdge(int x, int y, int c) {
G[x] = new Edge{y, c, 0, NULL, G[x]};
G[y] = new Edge{x, 0, 0, G[x], G[y]};
G[x]->rev = G[y];
}
int Aug() {
int d = INF;
for (int pos = n; preArc[pos]; pos = preArc[pos]->rev->to)
Reduce(d, preArc[pos]->cap - preArc[pos]->v);
for (int pos = n; preArc[pos]; pos = preArc[pos]->rev->to) {
preArc[pos]->v += d;
preArc[pos]->rev->v -= d;
}
return d;
}
long long Run() {
static int num[XN], d[XN];
static Edge *cArc[XN];
std::fill(num + 1, num + n, 0);
std::fill(d + 1, d + 1 + n, 0);
std::copy(G + 1, G + 1 + n, cArc + 1);
num[0] = n;
preArc[1] = 0;
long long flow = 0;
for (int pos = 1; d[1] < n;) {
if (pos == n) {
flow += Aug();
pos = 1;
}
bool adv = 0;
for (Edge *&e = cArc[pos]; e; e = e->pre) {
int u = e->to;
if (e->cap > e->v && d[u] + 1 == d[pos]) {
adv = 1;
preArc[pos = u] = e;
break;
}
}
if (!adv) {
if (--num[d[pos]] == 0)
break;
d[pos] = n;
for (Edge *e = cArc[pos] = G[pos]; e; e = e->pre)
if (e->cap > e->v)
Reduce(d[pos], d[e->to] + 1);
num[d[pos]]++;
if (pos != 1)
pos = preArc[pos]->rev->to;//cArc
}
}
return flow;
}
}
using namespace std;
int main() {
// freopen("02","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;
std::cin >> T;
while (T--) {
int m;
std::cin >> n >> m;
for (int i = 1; i <= n; ++i) {
D::G[i].clear();
I::G[i] = 0;
}
for (int i = 1; i <= m; ++i) {
int x, y, v;
std::cin >> x >> y >> v;
D::G[x].push_back({y, v});
}
D::Run();
for (int i = 0; i < 50; ++i) {
cout << sp[i] << endl;
}
if (sp[n] == oo)
std::cout << 0 << '\n';
else {
int addedEdgeNum = 0;
for (int pos = 1; pos <= n; ++pos)
for (auto &e : D::G[pos])
if (sp[e.to] - sp[pos] == e.v) {
I::AddEdge(pos, e.to, e.v);
++addedEdgeNum;
}
cout << addedEdgeNum << endl;
std::cout << I::Run() << std::endl;
}
}
return 0;
}