洛谷P3381 【模板】最小费用最大流

模板最小费用最大流

洛谷P3381 【模板】最小费用最大流

这题我用这个会T 只有 80分，感觉最小费用最大流就应该加一些常数优化，否则会非常慢

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream> 
  8 #include <iomanip>
  9 #include <queue> 
 10 #define inf 1e9 
 11 #define maxn 5005 
 12 #define maxm 50005 
 13 #define PAIR pair <int,int> 
 14 using namespace std ; 
 15 
 16 int n,m,s,t,x,y,vol,cost,gEdgeCount ; 
 17 
 18 PAIR ans ; 
 19 
 20 struct Edge{
 21     int to,vol,cost,next ; 
 22 };
 23 Edge gEdges[2*maxm] ;
 24 
 25 int gHead[maxn],gPre[maxn],gPath[maxn],gDist[maxn] ; 
 26 
 27 inline void InsertEdge(int u,int v,int vol,int cost) 
 28 {
 29     gEdges[gEdgeCount].to = v ; 
 30     gEdges[gEdgeCount].vol = vol ; 
 31     gEdges[gEdgeCount].cost = cost ;
 32     gEdges[gEdgeCount].next = gHead[u] ; 
 33     gHead[u] = gEdgeCount++ ; 
 34     
 35     gEdges[gEdgeCount].to = u ;  
 36     gEdges[gEdgeCount].vol = 0 ;
 37     gEdges[gEdgeCount].cost = -cost ;            //   取反  是为了之后能够退流   
 38     gEdges[gEdgeCount].next = gHead[v] ;   
 39     gHead[v] = gEdgeCount++ ; 
 40 }
 41 
 42 inline bool Spfa( int s,int t )  
 43 {
 44     for(int i=0;i<=n;i++) gPre[ i ] = -1 ; 
 45     for(int i=0;i<=n;i++) gDist[ i ] = 1e9 ; 
 46     gDist[ s ] = 0 ; 
 47     queue<int> Q ; 
 48     Q.push(s) ; 
 49     while(!Q.empty()) 
 50     {
 51         int u = Q.front() ; 
 52         Q.pop() ; 
 53         
 54         for(int e = gHead[u];e != -1 ;e = gEdges[e].next ) 
 55         {
 56             int v = gEdges[e].to ; 
 57             if(gEdges[e].vol>0&&gDist[u] + gEdges[e].cost < gDist[v]) 
 58             {
 59                 gDist[v] = gDist[u] + gEdges[e].cost ; 
 60                 gPre[v] = u ; 
 61                 gPath[v] = e ; 
 62                 Q.push(v) ; 
 63             }
 64         }
 65     }
 66      if(gPre[t]==-1) 
 67          return false ; 
 68      return true ; 
 69 }
 70 
 71 inline PAIR MinCostFlow(int s,int t) 
 72 {
 73     int cost = 0,flow = 0 ; 
 74     while(Spfa(s,t)) 
 75     {
 76         int f = inf ; 
 77         for(int u = t; u != s; u = gPre[u] ) 
 78             if(gEdges[gPath[u]].vol < f ) 
 79                 f = gEdges[gPath[u]].vol ;  
 80         flow+=f ; 
 81         cost+= gDist[t] * f ; 
 82         for(int u=t;u!=s;u=gPre[u] ) 
 83         {
 84             gEdges[gPath[u]].vol-=f ; 
 85             gEdges[gPath[u]^1].vol+=f ;  
 86         } 
 87     }
 88     PAIR ans ; 
 89     ans.first = flow ;   ans.second = cost ; 
 90     return ans ; 
 91 }
 92 
 93 int main() 
 94 {
 95     scanf("%d%d%d%d",&n,&m,&s,&t) ; 
 96     for(int i=0;i<=n;i++) gHead[ i ] = -1 ; 
 97     for(int i=1;i<=m;i++) 
 98     {
 99         scanf("%d%d%d%d",&x,&y,&vol,&cost) ;  
100         InsertEdge(x,y,vol,cost) ; 
101     }
102     ans = MinCostFlow(s,t) ; 
103     printf("%d %d
",ans.first,ans.second ) ; 
104     return 0 ; 
105 }

这个加了一下优化
然后就跑得比较快了 1400ms

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=1e4+10;
 4 const int maxm=1e5+10;
 5 const int maxt=2139062143;
 6 inline int min_(int x,int y){return x<y?x:y;}
 7 int n,m,s,t,nflow,nfee,flow,fee;
 8 int a,b,c,d;
 9 int h[maxn],hs=1;
10 int e_q[maxm],e_z[maxm],e_n[maxm],e_w[maxm],e_f[maxm];
11 int add(int q,int z,int k,int w,int f){e_q[k]=q,e_z[k]=z,e_n[k]=h[q],e_w[k]=w,e_f[k]=f,h[q]=k;}
12 int q[maxm],head,tail;
13 int w[maxn],p[maxn];
14 bool v[maxn];
15 int ap(int k,int v){
16     if(k==s) return v;
17     int ret=ap(e_q[p[k]],min_(v,e_w[p[k]]));
18     if(!e_f[p[k]^1]) add(k,e_q[p[k]],p[k]^1,0,-e_f[p[k]]);
19     e_w[p[k]]-=ret,e_w[p[k]^1]+=ret;
20     return ret;
21 } 
22 void Mcmf(){
23     while(1){
24         memset(w,0x7f,sizeof(w));
25         memset(v,0,sizeof(v));
26         head=tail=w[s]=0;
27         q[head++]=s,v[s]=1;
28         while(head>tail){
29             a=q[tail++],v[a]=0;
30             for(int i=h[a];i;i=e_n[i])
31             if(0ll+e_f[i]+w[a]<w[e_z[i]]&&e_w[i]){
32                 p[e_z[i]]=i;
33                 w[e_z[i]]=e_f[i]+w[a];
34                 if(!v[e_z[i]]) q[head++]=e_z[i],v[e_z[i]]=1;
35             }
36         }
37         if(w[t]==maxt) break;
38         nflow=ap(t,maxt);
39         flow+=nflow;
40         fee+=nflow*w[t];
41     }
42 }
43 int main(){
44     scanf("%d%d%d%d",&n,&m,&s,&t);
45     for(int i=1;i<=m;i++){
46         scanf("%d%d%d%d",&a,&b,&c,&d);
47         ++hs,add(a,b,hs,c,d),hs++;
48     }
49     Mcmf();
50     printf("%d %d
",flow,fee);
51     return 0;
52 }