题目链接 3381 【模板】最小费用最大流
手写堆版本 dijkstra 400+ms 看来优先队列的常数好大
#include<bits/stdc++.h> using namespace std; #define maxn 100001 #define inf 0x3f3f3f3f #define pii pair<int,int > inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9'){if(c=='-')flag=1; c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?-x:x; } struct ac{ int to,va,cos,nex; }eg[maxn*2]; struct wa{ int x,y; wa(){} wa(int a,int b){ x=a,y=b; } }aa[maxn*2]; int head[maxn],dis[maxn],pre[maxn],flow[maxn],h[maxn]; bool fa[maxn]; int n,m,s,t,maxflow=0,maxcost=0,tot=0,len=0; void init(){ tot=0; memset(eg,0,sizeof(eg)); memset(head,-1,sizeof(head)); memset(h,0,sizeof(h)); memset(pre,0,sizeof(pre)); } bool dcmp(wa A,wa B){ if(A.x<=B.x)return 1; return 0; } void add(int v){ if(v==1)return; if(dcmp(aa[v],aa[v/2]))swap(aa[v],aa[v/2]),add(v/2); } void updata(int v){ if(v*2>len)return; if(v*2==len) { if(dcmp(aa[v*2],aa[v]))swap(aa[v],aa[v*2]); return; } if(dcmp(aa[v],aa[v*2])&&dcmp(aa[v],aa[v*2+1]))return; if(dcmp(aa[v*2],aa[v*2+1]))swap(aa[v],aa[v*2]),updata(v*2); else swap(aa[v],aa[v*2+1]),updata(v*2+1); } void add_eg(int u,int to,int va,int cos){ eg[tot].va=va; eg[tot].cos=cos; eg[tot].to=to; eg[tot].nex=head[u]; head[u]=tot++; eg[tot].va=0; eg[tot].cos=-cos; eg[tot].to=u; eg[tot].nex=head[to]; head[to]=tot++; } bool dijstra(int s,int t){ memset(dis,inf,sizeof(dis)); dis[s]=0; flow[s]=inf; aa[++len]=wa(0,s); while(len){ wa x=aa[1]; swap(aa[1],aa[len--]); updata(1); int u=x.y; if(dis[x.y]<x.x) continue; for(int j=head[u];j!=-1;j=eg[j].nex){ int v=eg[j].to; int f=eg[j].cos; if(!fa[v]&&eg[j].va>0&&dis[v]>dis[u]+f+h[u]-h[v]){ dis[v]=dis[u]+f+h[u]-h[v]; flow[v]=min(flow[u],eg[j].va); pre[v]=j; aa[++len]=wa(dis[v],v); add(len); } } } if(dis[t]!=inf) return 1; return 0; } void work(){ while(dijstra(s,t)){ int z=t; while(z!=s){ int i=pre[z]; eg[i].va-=flow[t]; eg[i^1].va+=flow[t]; z=eg[i^1].to; } for(int j=1;j<=n;j++){ h[j]+=dis[j]; } maxflow+=flow[t]; maxcost+=flow[t]*h[t]; } } int main(){ cin>>n>>m>>s>>t; init(); for(int j=0;j<m;j++){ int x,y,a,b; //scanf("%d%d%d%d",&x,&y,&a,&b); x=read(); y=read();a=read();b=read(); add_eg(x,y,a,b); } work(); printf("%d %d\n",maxflow,maxcost); }
dijkstra 可能因为常数比较大 t了一个点但是 开o2之后可以轻松水过
dijkstra 版本 #include<bits/stdc++.h> using namespace std; #define maxn 100001 #define inf 0x3f3f3f3f #define pii pair<int,int > int head[maxn],dis[maxn],pre[maxn],flow[maxn],h[maxn]; struct ac{ int to,va,cos,nex; }eg[maxn]; int n,m,s,t,maxflow=0,maxcost=0,tot=0; void init(){ tot=0; memset(eg,0,sizeof(eg)); memset(head,-1,sizeof(head)); memset(h,0,sizeof(h)); memset(pre,0,sizeof(pre)); } void add_eg(int u,int to,int va,int cos){ eg[tot].va=va; eg[tot].cos=cos; eg[tot].to=to; eg[tot].nex=head[u]; head[u]=tot++; eg[tot].va=0; eg[tot].cos=-cos; eg[tot].to=u; eg[tot].nex=head[to]; head[to]=tot++; } bool dijstra(int s,int t){ memset(dis,inf,sizeof(dis)); memset(fa,0,sizeof(fa)); dis[s]=0; flow[s]=inf; fa[s]=1; priority_queue<pii,vector<pii>,greater<pii> >q; q.push(make_pair(0,s)); while(!q.empty()){ pii x=q.top(); q.pop(); int u=x.second; if(dis[x.second]<x.first) continue; for(int j=head[u];j!=-1;j=eg[j].nex){ int v=eg[j].to; int f=eg[j].cos; if(eg[j].va>0&&dis[v]>dis[u]+f+h[u]-h[v]){ dis[v]=dis[u]+f+h[u]-h[v]; flow[v]=min(flow[u],eg[j].va); pre[v]=j; q.push(make_pair(dis[v],v)); } } } if(dis[t]!=inf) return 1; return 0; } void work(){ while(dijstra(s,t)){ int z=t; while(z!=s){ int i=pre[z]; eg[i].va-=flow[t]; eg[i^1].va+=flow[t]; z=eg[i^1].to; } for(int j=1;j<=n;j++){ h[j]+=dis[j]; } maxflow+=flow[t]; maxcost+=flow[t]*h[t]; } } int main(){ cin>>n>>m>>s>>t; init(); for(int j=0;j<m;j++){ int x,y,a,b; scanf("%d%d%d%d",&x,&y,&a,&b); add_eg(x,y,a,b); } work(); cout<<maxflow<<" "<<maxcost<<endl; }
SPFA版本
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; #define maxn 100001 #define inf 0x3f3f3f3f int head[maxn],dis[maxn],pre[maxn],flow[maxn]; bool fa[maxn]; struct ac{ int to,va,cos,nex; }eg[maxn*2]; int n,m,s,t,maxflow=0,maxcost=0,tot=0; void init(){ tot=0; memset(eg,0,sizeof(eg)); memset(head,-1,sizeof(head)); } void add_eg(int u,int to,int va,int cos){ eg[tot].va=va; eg[tot].cos=cos; eg[tot].to=to; eg[tot].nex=head[u]; head[u]=tot++; eg[tot].va=0; eg[tot].cos=-cos; eg[tot].to=u; eg[tot].nex=head[to]; head[to]=tot++; } bool spfa(int s,int t){ memset(dis,inf,sizeof(dis)); memset(fa,0,sizeof(fa)); dis[s]=0; flow[s]=inf; fa[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); fa[u]=0; for(int j=head[u];j!=-1;j=eg[j].nex){ int v=eg[j].to; int f=eg[j].cos; //cout<<u<<" "<<v<<endl; if(eg[j].va&&dis[u]+f<dis[v]){ dis[v]=dis[u]+f; flow[v]=min(flow[u],eg[j].va); pre[v]=j; if(!fa[v]){ fa[v]=1; q.push(v); } } } } if(dis[t]!=inf) return 1; return 0; } void work(){ while(spfa(s,t)){ int z=t; while(z!=s){ int i=pre[z]; eg[i].va-=flow[t]; eg[i^1].va+=flow[t]; z=eg[i^1].to; } maxflow+=flow[t]; maxcost+=flow[t]*dis[t]; } } int main(){ cin>>n>>m>>s>>t; init(); for(int j=0;j<m;j++){ int x,y,a,b; cin>>x>>y>>a>>b; add_eg(x,y,a,b); } work(); cout<<maxflow<<" "<<maxcost<<endl; }
京公网安备 11010502036488号