【题意】：跟zoj 2760的一样。
【题解】：跟zoj 2760的一样，有一点点不同的是这题数据大了，不能用floyd，而且有重边。请参考我那个zoj 2760的题解，见谅。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 using namespace std;
6 #define inf 999999999
7 #define maxn 1005
8 #define maxm 300005
9
10 int n, m, s, t;
11 int eh[maxn], pre[maxn], cur[maxn], dist[maxn], cnt[maxn], tot, low[maxn];
12 int ddeh[maxn], tot1, dd[maxn], rddeh[maxn], rdd[maxn], tot2;
13 bool visit[maxn];
14 struct Edge {
15 int u, v, cap, flow, next;
16 }et[maxm];
17
18 struct Edge1 {
19 int u, v, w, next;
20 }ddet[maxm], rddet[maxm];
21
22 void isapinit() {
23 tot = tot1 = tot2 = 0;
24 memset(eh, -1, sizeof(eh));
25 memset(ddeh, -1, sizeof(ddeh));
26 memset(rddeh, -1, sizeof(rddeh));
27 }
28
29 void isapadd(int u, int v, int cap, int flow) {
30 Edge E = {u, v, cap, flow, eh[u]};
31 et[tot] = E;
32 eh[u] = tot++;
33 }
34
35 void isapaddedge(int u, int v, int cap) {
36 isapadd(u, v, cap, 0), isapadd(v, u, 0, 0);
37 }
38
39 void add1(int u, int v, int w) {
40 Edge1 E = {u, v, w, ddeh[u]};
41 ddet[tot1] = E;
42 ddeh[u] = tot1++;
43 }
44
45 void add2(int u, int v, int w) {
46 Edge1 E = {u, v, w, rddeh[u]};
47 rddet[tot2] = E;
48 rddeh[u] = tot2++;
49 }
50
51 int isap(int s, int t, int n) {
52 int u, v, now, flow = 0;
53 memset(dist, 0, sizeof(dist));
54 memset(cnt, 0, sizeof(cnt));
55 memset(low, 0, sizeof(low));
56 for(u = 0; u <= n; u++) cur[u] = eh[u];
57 low[s] = inf, cnt[0] = n;
58 u = s;
59 while(dist[s] < n) {
60 for(now = cur[u]; now != -1; now = et[now].next)
61 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
62 break;
63 if(now != -1) {
64 cur[u] = pre[v] = now;
65 low[v] = min(low[u], et[now].cap - et[now].flow);
66 u = v;
67 if(u == t) {
68 for(; u != s; u = et[pre[u]].u) {
69 et[pre[u]].flow += low[t];
70 et[pre[u]^1].flow -= low[t];
71 }
72 low[s] = inf, flow += low[t];
73 }
74 } else {
75 if(--cnt[dist[u]] == 0) break;
76 dist[u] = n;
77 cur[u] = eh[u];
78 for(now = cur[u]; now != -1; now = et[now].next)
79 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
80 dist[u] = dist[et[now].v] + 1;
81 cnt[dist[u]]++;
82 }
83 }
84 return flow;
85 }
86
87 bool spfa(int s, Edge1 ddet[], int ddeh[], int dd[]) {
88 for(int i = 0; i <= n; i++) visit[i] = 0, dd[i] = inf;
89 dd[s] = 0, visit[s] = 1;
90 queue<int> que;
91 que.push(s);
92 while(!que.empty()) {
93 int u = que.front();
94 que.pop(), visit[u] = 0;
95 for(int i = ddeh[u]; i != -1; i = ddet[i].next) {
96 int v = ddet[i].v;
97 if(dd[v] > ddet[i].w + dd[u]) {
98 dd[v] = ddet[i].w + dd[u];
99 if(!visit[v]) {
100 visit[v] = 1;
101 que.push(v);
102 }
103 }
104 }
105 }
106 return true;
107 }
108
109 int main() {
110 int T, u, v, w;
111 scanf("%d", &T);
112 while(T--) {
113 isapinit();
114 scanf("%d%d", &n, &m);
115 for(int i = 0; i < m; i++) {
116 scanf("%d%d%d", &u, &v, &w);
117 add1(u, v, w);
118 add2(v, u, w);
119 }
120 scanf("%d%d", &s, &t);
121 spfa(s, ddet, ddeh, dd);
122 spfa(t, rddet, rddeh, rdd);
123 for(int i = 0; i < tot1; i++) {
124 u = ddet[i].u, v = ddet[i].v, w = ddet[i].w;
125 if(dd[u] + w + rdd[v] == dd[t])
126 isapaddedge(u, v, 1);
127 }
128 printf("%d\n", isap(s, t, n));
129 }
130 return 0;
131 }