luogu P4015 运输问题
// luogu-judger-enable-o2 #include<queue> #include<cstdio> #include<cstring> #include<algorithm> #define INF 0x7fffffff const int maxn = 2007; using std::min; using std::queue; int dis[maxn];bool vis[maxn]; inline int read() { int x=0,f=1; char c=getchar() ; while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } int S,T,n,m,pre[maxn],Min_Cost; struct node{ int u,v,cost,flow,next; }edge[(maxn*10)<<1]; int num=1,head[maxn]; void add_edge(int u,int v,int w,int cost) { edge[++num].v=v;edge[num].u=u;edge[num].flow=w;edge[num].cost=cost,edge[num].next=head[u],head[u]=num; } bool spfa() { memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof dis); queue<int>que; que.push(S);vis[S]=1,dis[S]=0; while(!que.empty()) { int x=que.front();que.pop(); for(int i=head[x];i;i=edge[i].next ) { int v=edge[i].v; if(dis[x]+edge[i].cost<dis[v]&&edge[i].flow>0) { pre[v]=i; dis[v]=dis[x]+edge[i].cost; if(!vis[v])vis[v]=1,que.push(v); } } vis[x]=0; } return dis[T]!=0x3f3f3f3f; } void calc() { int MF=0x3f3f3f3f; for(int i=T;i!=S;i=edge[pre[i]].u) MF=min(MF,edge[pre[i]].flow); for(int i=T;i!=S;i=edge[pre[i]].u) { edge[pre[i]].flow-=MF; edge[pre[i]^1].flow+=MF; Min_Cost+=edge[pre[i]].cost*MF; } } void MFMC() { while(spfa()) calc(); } int co[107][207]; int ra[107],rb[107]; int main() { m=read();n=read();S=0,T=m+n+1; for(int i=1;i<=m;++i) add_edge(S,i,ra[i]=read(),0),add_edge(i,S,0,0); for(int i=1;i<=n;++i) add_edge(m+i,T,rb[i]=read(),0),add_edge(T,m+i,0,0); for(int i=1;i<=m;++i) for(int j=m+1;j<=m+n;++j) add_edge(i,j,INF,co[i][j]=read()),add_edge(j,i,0,-co[i][j]); MFMC();printf("%d\n",Min_Cost); Min_Cost=0,num=1,memset(head,0,sizeof head); for(int i=1;i<=m;++i) add_edge(S,i,ra[i],0),add_edge(i,S,0,0); for(int i=1;i<=n;++i) add_edge(m+i,T,rb[i],0),add_edge(T,m+i,0,0); for(int i=1;i<=m;++i) for(int j=m+1;j<=m+n;++j) add_edge(i,j,INF,-co[i][j]),add_edge(j,i,0,co[i][j]); MFMC(); printf("%d\n",-Min_Cost); return 0; }转载于:https://www.cnblogs.com/sssy/p/8562941.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip