HDU - 3416：

参考：

题意：

　　　问一个带权值的图中，最多能跑几次最短路，每条路只能走一遍。

思路：

　　这道题要利用最大流算法和最短路算法。先要跑两遍dji（），第一遍跑从起点S开始跑一遍正图，第二遍从终点T跑一遍反图。这样后枚举每一条边，看这条边的起点到S的距离+这条边的终点到T的距离+这条边长 == 最短路，如果成立，就把这条边 的容量设为1，加入网络流的图中。最后跑一下最大流就行了。

　　自己在枚举点的时候没有搞清楚终点是T，wa了好几发。

#include 
      
       #include  
       
        #include  
        
         #include   
         
          #include   
          
           #include   
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     

, greater

>que;const ll mos = 0x7FFFFFFF; //2147483647const ll nmos = 0x80000000; //-2147483648const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18const int mod = 1e9+7;const double esp = 1e-8;const double PI=acos(-1.0);template

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

g[2][maxn]; //dji void dji(int f,int soc){ for(int i=1; i<=n; i++)dis[f][i] = inf; priority_queue

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

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

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

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

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

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