最短路+最大流

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int maxn=1000+10;const int MAXN=100000+10;const int INF=0x7FFFFFFF;struct Edge{ int from,to,cap,flow;};vector
            
             edges;vector
             
              G[maxn];struct EE1{ int from,to,w;} ee1[MAXN];struct EE2{ int from,to,w;} ee2[MAXN];vector
              
               SPFAG1[maxn];vector
               
                SPFAG2[maxn];bool vis[maxn];int d[maxn];int cur[maxn];int U[MAXN],V[MAXN],C[MAXN];int FF1[maxn],Dis1[maxn],FF2[maxn],Dis2[maxn];int n,m,s,t,N,M;//求出层次网络bool BFS(){ memset(vis,0,sizeof(vis)); queue
                
                 Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0; i
                 
                  e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t];}//加边void AddEdge(int from,int to,int cap){ Edge r; r.from=from; r.to=to; r.cap=cap; r.flow=0; edges.push_back(r); Edge d; d.from=to; d.to=from; d.cap=0; d.flow=0; edges.push_back(d); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1);}//每个阶段来一次DFS增广int DFS(int x,int a){ if(x==t||a==0) return a; int flow=0,f; for(int i=cur[x]; i
                  
                   0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow;}//多个阶段，多次建立层次网络。int Maxflow(int ss,int tt){ int flow=0; while(BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(ss,INF); } return flow;}void SPFA1(){ for(int i=0; i<=N; i++) Dis1[i]=INF; queue
                   
                    Q; Q.push(s); FF1[s]=1; Dis1[s]=0; while(!Q.empty()) { int h=Q.front(); Q.pop(); FF1[h]=0; for(int i=0; i
                    

Q; Q.push(t); FF2[t]=1; Dis2[t]=0; while(!Q.empty()) { int h=Q.front(); Q.pop(); FF2[h]=0; for(int i=0; i