洛谷P4015 运输问题(费用流)

传送门

源点向仓库连费用$0$,流量为储量的边,商店向汇点连费用$0$,流量为需求的边,然后仓库向商店连流量$inf$,费用对应的边,跑个费用流即可

 //minamoto
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,M=;
int ver[M],Next[M],head[N],edge[M],flow[M],tot=;
int dis[N],disf[N],n,m,s,t,ans,Pre[N],last[N],vis[N],x;
queue<int> q;
inline void add(int u,int v,int e,int f){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e,flow[tot]=f;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=-e,flow[tot]=;
}
bool spfa_min(){
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
memset(disf,0x3f,sizeof(disf));
q.push(s),dis[s]=,vis[s]=,Pre[t]=-;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(flow[i]>&&dis[v]>dis[u]+edge[i]){
dis[v]=dis[u]+edge[i],Pre[v]=u;
last[v]=i,disf[v]=min(disf[u],flow[i]);
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return Pre[t]!=-;
}
int dinic_min(){
int maxflow=,mincost=;
while(spfa_min()){
int u=t;
maxflow+=disf[t],mincost+=disf[t]*dis[t];
while(u!=s){
flow[last[u]]-=disf[t];
flow[last[u]^]+=disf[t];
u=Pre[u];
}
}
return mincost;
}
bool spfa_max(){
memset(dis,0xef,sizeof(dis));
memset(vis,,sizeof(vis));
memset(disf,0x3f,sizeof(disf));
q.push(s),dis[s]=,vis[s]=,Pre[t]=-;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(flow[i]>&&dis[v]<dis[u]+edge[i]){
dis[v]=dis[u]+edge[i],Pre[v]=u;
last[v]=i,disf[v]=min(disf[u],flow[i]);
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return Pre[t]!=-;
}
int dinic_max(){
int maxflow=,maxcost=;
while(spfa_max()){
int u=t;
maxflow+=disf[t],maxcost+=disf[t]*dis[t];
while(u!=s){
flow[last[u]]-=disf[t];
flow[last[u]^]+=disf[t];
u=Pre[u];
}
}
return maxcost;
}
int main(){
m=read(),n=read();
s=,t=n+m+;
for(int i=;i<=m;++i){
int x=read();
add(s,i,,x);
}
for(int i=m+;i<=n+m;++i){
int x=read();
add(i,t,,x);
}
for(int i=;i<=m;++i)
for(int j=;j<=n;++j){
int x=read();
add(i,j+m,x,inf);
}
printf("%d\n",dinic_min());
for(int i=;i<=tot;i+=) flow[i]+=flow[i^],flow[i^]=;
printf("%d\n",dinic_max());
return ;
}
上一篇:Windows cd


下一篇:[Android Studio] Android Studio移除的Module如何恢复(转载)