https://vjudge.net/problem/HDU-6582
#include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<vector> #include<string> #include<cstring> #include<queue> using namespace std; const int maxn=1e4+10; const long long inf=1e16; struct SimpleEdge { int from,to; long long dis; SimpleEdge(int from,int to,long long dis) { this->from=from,this->to=to,this->dis=dis; } }; struct Node { int id; long long dis; Node(int id,long long dis) { this->id=id,this->dis=dis; } bool operator<(const Node &r)const { return this->dis>r.dis; } }; struct Edge { int from,to; long long cap,flow; Edge(int fr,int to,long long ca,long long fl) { this->from=fr,this->to=to,this->cap=ca,this->flow=fl; } }; struct Dinic { vector<int> G[maxn]; vector<Edge> edges; bool vis[maxn]; int n,s,t,cur[maxn]; long long d[maxn]; void init(int s,int t,int n) { this->s=s,this->t=t; this->n=n; for(int i=1;i<=n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,long long cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); G[from].push_back(edges.size()-2); G[to].push_back(edges.size()-1); } bool bfs() { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0,vis[s]=true; while(!Q.empty()) { int now=Q.front();Q.pop(); for(int i=0,_size=G[now].size();i<_size;i++) { Edge &e=edges[G[now][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to]=true; d[e.to]=d[now]+1; Q.push(e.to); } } } return vis[t]; } int dfs(int x,long long a) { if(x==t||a==0) return a; long long flow=0,f; for(int &i=cur[x],_size=G[x].size();i<_size;i++) { Edge &e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(!a) break; } } return flow; } long long MaxFlow() { long long ans=0; while(bfs()) { memset(cur,0,sizeof(cur)); ans+=dfs(s,inf); } return ans; } }maxflow; vector<int> G[maxn]; vector<SimpleEdge> edges; int n,m,from,to; long long dis,d[maxn]; bool done[maxn]; void init_all() { edges.clear(); for(int i=1;i<=n;i++) G[i].clear(); maxflow.init(1,n,n); } int main() { // freopen("in.txt","r",stdin); int T;scanf("%d",&T);while(T--) { scanf("%d %d",&n,&m);init_all(); while(m--) { scanf("%d %d %lld",&from,&to,&dis); edges.push_back(SimpleEdge(from,to,dis)); G[from].push_back(edges.size()-1); } for(int i=1;i<=n;i++) d[i]=inf; memset(done,0,sizeof(done)); d[1]=0;priority_queue<Node> nodes; nodes.push(Node(1,0)); while(!nodes.empty()) { int now=nodes.top().id; nodes.pop(); if(done[now]) continue; done[now]=true; for(int x=0,_size=G[now].size();x<_size;x++) { SimpleEdge &e=edges[G[now][x]]; if(e.dis+d[now]<d[e.to]) { d[e.to]=e.dis+d[now]; nodes.push(Node(e.to,d[e.to])); } } } for(int i=1;i<=n;i++) { for(int x=0,_size=G[i].size();x<_size;x++) { SimpleEdge &e=edges[G[i][x]]; if(d[e.to]==e.dis+d[e.from]) { maxflow.AddEdge(e.from,e.to,e.dis); } } } printf("%lld\n",maxflow.MaxFlow()); } return 0; }