HDU - 3416：http://acm.hdu.edu.cn/showproblem.php?pid=3416
参考：https://www.cnblogs.com/kuangbin/archive/2013/05/04/3059372.html
题意：
问一个带权值的图中，最多能跑几次最短路，每条路只能走一遍。
思路：
这道题要利用最大流算法和最短路算法。先要跑两遍dji（），第一遍跑从起点S开始跑一遍正图，第二遍从终点T跑一遍反图。这样后枚举每一条边，看这条边的起点到S的距离+这条边的终点到T的距离+这条边长 == 最短路，如果成立，就把这条边 的容量设为1，加入网络流的图中。最后跑一下最大流就行了。
自己在枚举点的时候没有搞清楚终点是T，wa了好几发。
#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> using namespace std; //#pragma GCC optimize(3) //#pragma comment(linker, "/STACK:102400000,102400000") //c++ #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue typedef long long ll; typedef unsigned long long ull; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q //priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q #define fi first #define se second //#define endl ' ' #define OKC ios::sync_with_stdio(false);cin.tie(0) #define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行 #define REP(i , j , k) for(int i = j ; i < k ; ++i) //priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 1e9+7; const double esp = 1e-8; const double PI=acos(-1.0); template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /*-----------------------showtime----------------------*/ const int maxn = 2e5+9; int n,m,c,ans; int dis[2][maxn]; vector<pii>g[2][maxn]; //dji void dji(int f,int soc){ for(int i=1; i<=n; i++)dis[f][i] = inf; priority_queue<pii>que; dis[f][soc] = 0; que.push(pii(0,soc)); while(!que.empty()){ pii tmp = que.top();que.pop(); int u = tmp.se; if(dis[f][u] < -1*tmp.fi)continue; for(int i=0; i<g[f][u].size(); i++){ int v = g[f][u][i].fi; if(dis[f][v] > dis[f][u] + g[f][u][i].se) { dis[f][v] = dis[f][u] + g[f][u][i].se; que.push(pii(-1*dis[f][v], v)); } } } } const int maxm = 1e6+9; struct Edge { int u,v,cap; Edge(){} Edge(int u,int v,int cap):u(u),v(v),cap(cap){} }es[maxm]; int R,S,T; vector<int>tab[maxn]; int diss[maxn],current[maxn]; void addedge(int u,int v,int cap){ tab[u].pb(R); es[R++] = Edge(u,v,cap); tab[v].pb(R); es[R++] = Edge(v,u,0); } bool BFS(){ queue<int>q;q.push(S); memset(diss,inf,sizeof(diss)); diss[S] = 0; while(!q.empty()){ int h = q.front();q.pop(); for(int i=0; i<tab[h].size(); i++){ Edge & e = es[tab[h][i]]; if(e.cap>0 &&diss[e.v] == inf){ diss[e.v] = diss[h] + 1; q.push(e.v); } } } return diss[T] < inf; } int DFS(int x,int maxflow){ if(x == T){ return maxflow; } for(int i=current[x]; i<tab[x].size(); i++){ current[x] = i; Edge &e = es[tab[x][i]]; if(diss[e.v] == diss[x] + 1 && e.cap > 0){ int flow = DFS(e.v, min(maxflow, e.cap)); if(flow>0){ e.cap -= flow; es[tab[x][i] ^ 1].cap += flow; return flow; } } } return 0; } int dinic(){ int ans = 0; while(BFS()){ int flow; memset(current,0,sizeof(current)); while(true){ flow = DFS(S,inf); if(flow > 0) ans += flow; else break; } } return ans; } int main(){ int t;scanf("%d" , &t); while(t--){ scanf("%d%d", &n, &m); for(int i=1; i<=n; i++)g[0][i].clear(),g[1][i].clear(),tab[i].clear(); for(int i=1; i<=m; i++){ int u,v,c; scanf("%d%d%d", &u, &v, &c); if(v == u)continue; g[0][u].pb(pii(v,c)); g[1][v].pb(pii(u,c)); } scanf("%d%d", &S, &T); dji(0,S),dji(1,T); // debug(dis[0][n]); R = 0; for(int i=1; i<=n; i++){ for(int j=0; j<g[0][i].size(); j++){ int u = i,v = g[0][i][j].fi; if(u!=v && dis[0][T] == dis[0][u] + dis[1][v] + g[0][i][j].se){ addedge(u,v,1); } } } printf("%d ", dinic()); } return 0; }