![[AHOI 2006] 上学路线（最短路+网络流）](http://47.106.118.63/wp-content/uploads/2018/08/光之教堂.jpg)
撰写Description
可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。 可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！” 合肥市一共设有N个公交车站，不妨将它们编号为1…N的自然数，并认为可可和卡卡家住在1号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N) 两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。 [任务] 编写一个程序： 从输入文件中读取合肥市公交路线的信息； 计算出实际上可可和卡卡上学需要花费的最少时间； 帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的ci和最小；向输出文件输出答案。
Input
输入文件中第一行有两个正整数N和M，分别表示合肥市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第(i+1)行）用四个正整数描述第i条路线：pi, qi, ti, ci；具体含义见上文描述。
Output
输出文件最多有两行。 第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。 第二行输出一个整数C,表示Ci之和
Sample Input
6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
Sample Output
2
5
5
HINT
2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000
合肥市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。
- 题解
- 首先得dijkstra求出最短路网络（找边的方法是 if (dist[u[i]] + w[i] == dist[v[i]]) addedgeF(u[i] , v[i] , c[i])）
- 然后要使得最短路变长，就等于在最短路网络内求一个最小割（题中说求出来没有路线也是可以的，所以不必考虑这种特殊情况）
- 按照最小割最大流定理，我们只要跑一个dinic即可
- 代码
-
-
#include<bits/stdc++.h> using namespace std; #define MAXN 500010 const int inf = 2e9; struct edge { int to , w , nxt; } e[MAXN << 1]; int n , tot , m; int u[MAXN] , v[MAXN] , w[MAXN] , c[MAXN] , head[MAXN] , depth[MAXN] , dist[MAXN]; bool visited[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v , int w) { ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot; } inline void addedgeF(int u , int v , int w) { ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot; ++tot; e[tot] = (edge){u , 0 , head[v]}; head[v] = tot; } inline void dijkstra() { priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > > q; for (int i = 1; i <= n; i++) { dist[i] = inf; visited[i] = false; } dist[1] = 0; q.push(make_pair(0 , 1)); while (!q.empty()) { int cur = q.top().second; q.pop(); if (visited[cur]) continue; visited[cur] = true; for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (dist[cur] + w < dist[v]) { dist[v] = dist[cur] + w; q.push(make_pair(dist[v] , v)); } } } } inline bool bfs() { int l , r; static int q[MAXN]; memset(depth , 0 , sizeof(depth)); q[depth[l = r = 1] = 1] = 1; while (l <= r) { int cur = q[l++]; for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (w > 0 && !depth[v]) { depth[v] = depth[cur] + 1; q[++r] = v; } } } if (depth[n] > 0) return true; else return false; } inline int dinic(int u , int flow) { int rest = flow; if (u == n) return flow; for (int i = head[u]; i && rest; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (depth[v] == depth[u] + 1 && w > 0) { int k = dinic(v , min(rest , w)); if (!k) depth[v] = 0; e[i].w -= k; e[i ^ 1].w += k; rest -= k; } } return flow - rest; } int main() { read(n); read(m); for (int i = 1; i <= m; i++) { read(u[i]); read(v[i]); read(w[i]); read(c[i]); addedge(u[i] , v[i] , w[i]); addedge(v[i] , u[i] , w[i]); } dijkstra(); printf("%d\n" , dist[n]); tot = 1; for (int i = 1; i <= n; i++) head[i] = 0; for (int i = 1; i <= m; i++) { if (dist[u[i]] + w[i] == dist[v[i]]) addedgeF(u[i] , v[i] , c[i]); if (dist[v[i]] + w[i] == dist[u[i]]) addedgeF(v[i] , u[i] , c[i]); } int ans = 0; while (bfs()) { while (int flow = dinic(1 , inf)) ans += flow; } printf("%d\n" , ans); return 0; }
-
-