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 94 95 96 97
|
using namespace std; const int maxn=2e5+50; typedef long long ll; ll S,T,From[maxn],Laxt[maxn],Next[maxn],To[maxn],Cap[maxn],cnt; ll vd[maxn],dis[maxn]; void (int u,int v,ll c){ Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;Cap[cnt]=c;From[cnt]=u; Next[++cnt]=Laxt[v];Laxt[v]=cnt;To[cnt]=u;Cap[cnt]=0;From[cnt]=v; } ll sap(int u,ll flow,ll limit){ if(u==T||flow==0)return flow; int tmp,delta=0; for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[u]==dis[v]+1&&Cap[i]){ tmp=sap(v,min(flow-delta,Cap[i]),limit); Cap[i]-=tmp;Cap[i^1]+=tmp;delta+=tmp; if(dis[S]>=(limit)||delta==flow)return delta; } } vd[dis[u]]--;if(!vd[dis[u]])dis[S]=limit; vd[++dis[u]]++; return delta; } void init(int limit){ cnt=1; for(int i=0;i<=limit;i++)Laxt[i]=dis[i]=vd[i]=0; } ll dist1[maxn]; ll dist2[maxn]; ll a[maxn],b[maxn],c[maxn]; struct node{ int u,v; ll w; }; struct no{ int id; ll w; bool operator <(const no &a)const{ return this->w>a.w; } }; vector<node>G[maxn]; void dij(ll d[],int n,int S){ for(int i=1;i<=n;i++)d[i]=1e18; d[S]=0; priority_queue<no>Q; Q.push({S,d[S]}); while(!Q.empty()){ no tmp=Q.top(); Q.pop(); int u=tmp.id; for(int i=0;i<G[u].size();i++){ node k=G[u][i]; int v=k.v,w=k.w; if(d[v]>d[u]+w){ d[v]=d[u]+w; Q.push({v,d[v]}); } } } }
int main(){ std::ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; init(n+2); for(int i=1;i<=n;i++)G[i].clear(); for(int i=1;i<=m;i++){ cin>>a[i]>>b[i]>>c[i]; G[a[i]].push_back({a[i],b[i],c[i]}); } S=1;T=n; dij(dist1,n,S); for(int i=1;i<=n;i++)G[i].clear(); for(int i=1;i<=m;i++){ G[b[i]].push_back({b[i],a[i],c[i]}); } dij(dist2,n,T); for(int i=1;i<=m;i++){ if(a[i]!=b[i]&&dist1[a[i]]+c[i]+dist2[b[i]]==dist1[T]){ add(a[i],b[i],c[i]); } } ll ans=0; while(dis[S]<n+2){ ans+=sap(S,1e18,n+2); } cout<<ans<<endl; } return 0; }
|
近期评论