1 #include <iostream>  2 #include <cstring>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cmath>  6 #include <string>  7 #include <vector>  8 #include <list>  9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <bitset> 13 #include <algorithm> 14 #include <numeric> 15 #include <functional> 16 #include <set> 17 #include <fstream> 18  19 using namespace std; 20  21 const int INF=0x3f3f3f3f; 22 const int maxm=10000010; 23 const int maxn=1010; 24  25 int N,M; 26 struct edge{ 27     int u,v,cap,next; 28 }G[maxm]; 29 int head[maxn*maxn],pre[maxn*maxn],level[maxn*maxn]; 30 int num[maxn*maxn],cur[maxn*maxn]; 31 int idx; 32 int s,t,tt; 33 struct edges{ 34     int v,w,next; 35 }road[maxm]; 36 int head1[maxn*2],used[maxn*2],d[maxn*2]; 37 int idx1; 38  39 void add_road(int u,int v,int w) 40 { 41     road[idx1].v=v; 42     road[idx1].w=w; 43     road[idx1].next=head1[u]; 44     head1[u]=idx1++; 45 } 46  47 void SPFA() 48 { 49     memset(d,INF,sizeof(d)); 50     memset(used,0,sizeof(used)); 51     queue<int> q; 52     q.push(s); 53     d[s]=0; 54     while(!q.empty()) 55     { 56         int u=q.front(); 57         q.pop(); 58         used[u]=0; 59         for(int i=head1[u];i!=-1;i=road[i].next) 60         { 61             int v=road[i].v; 62             if(d[v]>d[u]+road[i].w){ 63                 d[v]=d[u]+road[i].w; 64                 if(!used[v]){ 65                     used[v]=1; 66                     q.push(v); 67                 } 68             } 69         } 70     } 71 } 72  73 void build(int u,int v,int cap) 74 { 75     G[idx].v=v; 76     G[idx].cap=cap; 77     G[idx].next=head[u]; 78     head[u]=idx++; 79 } 80  81 void add_edge(int u,int v,int cap) 82 { 83     build(u,v,cap); 84     build(v,u,0); 85 } 86  87 void bfs() 88 { 89     memset(level,-1,sizeof(level)); 90     memset(num,0,sizeof(num)); 91     queue<int> q; 92     q.push(t); 93     level[t]=0; 94     num[0]=1; 95     while(!q.empty()) 96     { 97         int u=q.front(); 98         q.pop(); 99         for(int i=head[u];i!=-1;i=G[i].next)100         {101             int v=G[i].v;102             if(level[v]==-1){103                 level[v]=level[u]+1;104                 num[level[v]]++;105                 q.push(v);106             }107         }108     }109 }110 111 void ISAP()112 {113     memcpy(cur,head,sizeof(cur));114     bfs();115     int flow=0;116     int u=pre[s]=s;117     while(level[s]<tt)118     {119         if(u==t){120             int f=INF,pos;121             for(int i=s;i!=t;i=G[cur[i]].v)122             {123                 if(f>G[cur[i]].cap){124                     f=G[cur[i]].cap;125                     pos=i;126                 }127             }128             for(int i=s;i!=t;i=G[cur[i]].v)129             {130                 G[cur[i]].cap-=f;131                 G[cur[i]^1].cap+=f;132             }133             flow+=f;134             u=pos;135         }136         int k;137         for(k=cur[u];k!=-1;k=G[k].next)138         {139             if(level[G[k].v]+1==level[u]&&G[k].cap) break;140         }141         if(k!=-1){142             cur[u]=k;143             pre[G[k].v]=u;144             u=G[k].v;145         }else{146             if(--num[level[u]]==0) break;147             int mind=tt;148             for(int i=head[u];i!=-1;i=G[i].next)149             {150                 if(mind>level[G[i].v]&&G[i].cap){151                     mind=level[G[i].v];152                     cur[u]=i;153                 }154             }155             level[u]=mind+1;156             num[level[u]]++;157             u=pre[u];158         }159     }160     printf("%d\n",flow);161 }162 163 void build_graph()164 {165     for(int i=1;i<=N;i++)166     {167         for(int j=head1[i];j!=-1;j=road[j].next)168         {169             if(d[road[j].v]==d[i]+road[j].w){170                 add_edge(i,road[j].v,1);171             }172         }173     }174 }175 int main()176 {177 //    freopen("/Users/apple/Desktop/暑假/29(2)/29(2)/in","r",stdin);178     int T;179     scanf("%d",&T);180     while(T--)181     {182         idx=0;183         memset(head,-1,sizeof(head));184         idx1=0;185         memset(head1,-1,sizeof(head1));186         scanf("%d%d",&N,&M);187         tt=N+1;188         for(int i=0;i<M;i++)189         {190             int u,v,w;191             scanf("%d%d%d",&u,&v,&w);192             if(u==v) continue;193             else add_road(u, v, w);194         }195         scanf("%d%d",&s,&t);196         SPFA();197         build_graph();198         ISAP();199     }200     return 0;201 }