BZOJ 1266: [AHOI2006]上学路线route

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

Sample Output

HINT

2<=N<=500, 1<=M<=124,750, 1<=ti, ci<=10,000

合肥市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。

Solution

Floyd求出最短路，扫描每一条边，如果在最短路上就加入网络流，跑最小割即可。

这题由于没考虑到了正反都有边，把

写成了

于是成功的WA了QAQ…

Code

 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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1000000007;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
const int maxm = 520005;
struct edge_type {
    int to, next, r;
} edge[maxm];
int Q[666], cnte = 1, h[666], cur[666], S, T, d[666];
void ins(int x, int y, int z) {
    edge[++cnte].to = y;
    edge[cnte].next = h[x];
    edge[cnte].r = z;
    h[x] = cnte;
    edge[++cnte].to = x;
    edge[cnte].next = h[y];
    edge[cnte].r = 0;
    h[y] = cnte;
}
bool BFS() {
    int head = 0, tail = 1;
    for (int i = 0; i <= T; ++i) d[i] = -1;
    Q[0] = S; d[S] = 1;
    int now;
    while (head < tail) {
        now = Q[head++];
        for (int i = h[now]; i; i = edge[i].next) {
            if (edge[i].r && d[edge[i].to] == -1) {
                d[edge[i].to] = d[now] + 1;
                Q[tail++] = edge[i].to;
            }
        }
    }
    return (d[T]!=-1);
}
int dfs(int now, int a) {
    if (a == 0 || now == T) return a;
    int ret = 0, f;
    for (int &i = cur[now]; i; i = edge[i].next) {
        if (d[edge[i].to] != d[now] + 1) continue;
        if (f = dfs(edge[i].to, min(a, edge[i].r))) {
            ret += f;
            a -= f;
            edge[i].r -= f;
            edge[i^1].r += f;
        }
        if (!a) break;
    }
    if (!ret) d[now] = -1;
    return ret;
}
int A[maxm>>2], B[maxm>>2], C[maxm>>2], D[maxm>>2];
int F[666][666];
int main() {
    int n = getint(), m = getint();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            F[i][j] = INF;
        F[i][i] = 0;
    }
    S = 1; T = n;
    for (int i = 1; i <= m; ++i) {
        A[i] = getint(); B[i] = getint(); C[i] = getint(); D[i] = getint();
        F[A[i]][B[i]] = F[B[i]][A[i]] = min(C[i], F[A[i]][B[i]]);
    }
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                F[i][j] = min(F[i][j], F[i][k] + F[k][j]);
    int ans1 = F[1][n];
    for (int i = 1; i <= m; ++i) {
        if (F[1][A[i]] + C[i] + F[B[i]][n] == ans1) {
            ins(A[i], B[i], D[i]);
        }
        if (F[1][B[i]] + C[i] + F[A[i]][n] == ans1) {
            ins(B[i], A[i], D[i]);
        }
    }
    int ans2 = 0;
    while (BFS()) {
        for (int i = S; i <= T; ++i) cur[i] = h[i];
        ans2 += dfs(S, INF);
    }
    printf("%d\n%d", ans1, ans2);
    return 0;
}