学步园

赤裸裸的最小费用最大流。构建超级源点和超级汇点，源点出边的容量等于对应节点的储量，汇点入边的容量等于对应节点的需求量。

总结：本题因为用数组做队列时预留的空间不够，贡献了数次RE。

#include <iostream><br /> using namespace std;<br /> #define MAXN 105<br /> #define MIN(x,y) (x<y?x:y)<br /> #define INF 2000005<br /> int map[MAXN][MAXN],cost[MAXN][MAXN];<br /> int pre[MAXN],min_flow[MAXN];//记录结点的父节点 当前路径中最小的一段的值，也即限制值<br /> int flow[MAXN][MAXN];//记录当前网络中的流<br /> int dist[MAXN];//SPFA用<br /> bool SPFA(int num,int source,int sink)<br /> {<br /> int my_queue[MAXN*100];//数组实现队列，必须预留比较大的空间<br /> for(int i=0;i<num;i++)<br /> {<br /> dist[i]=INF;<br /> }<br /> dist[source]=0;<br /> int queue_first=0;//初始化队列<br /> int queue_end=0;<br /> my_queue[queue_end++]=source;<br /> memset(pre,-1,sizeof(pre));<br /> min_flow[source]=INF;<br /> while(queue_first<queue_end)<br /> {<br /> int temp=my_queue[queue_first++];<br /> for(int i=0;i<num;i++)<br /> {<br /> if((map[temp][i]-flow[temp][i]>0)&&(dist[temp]+cost[temp][i]<dist[i]))<br /> {<br /> dist[i]=dist[temp]+cost[temp][i];<br /> my_queue[queue_end++]=i;//加入队列<br /> pre[i]=temp;<br /> min_flow[i]=MIN(min_flow[temp],(map[temp][i]-flow[temp][i]));//求得min_flow<br /> }<br /> }<br /> }<br /> if(pre[sink]!=-1) return true;//sink的父节点不为初始值，说明已经找到了一条路径<br /> return false;<br /> }<br /> int Min_Cost_Max_Flow(int num,int source,int sink)//参数含义：结点数量 源点 汇点<br /> {<br /> int ans=0;<br /> memset(flow,0,sizeof(flow));<br /> while(SPFA(num,source,sink))//一直循环，直到不存在增广路径<br /> {<br /> int k=sink;<br /> while(pre[k]>=0)<br /> {<br /> flow[pre[k]][k]+=min_flow[sink];//将新的流量加入flow<br /> flow[k][pre[k]]=-flow[pre[k]][k];<br /> k=pre[k];<br /> }<br /> ans+=dist[sink]*min_flow[sink];<br /> }<br /> return ans;<br /> }<br /> int main()<br /> {<br /> int N,M,K,ans;<br /> bool no_ans;<br /> int order[MAXN][MAXN],storage[MAXN][MAXN];<br /> while(scanf("%d%d%d",&N,&M,&K)&&N!=0)<br /> {<br /> no_ans=false;<br /> ans=0;<br /> for(int i=0;i<N;i++)<br /> {<br /> for(int j=0;j<K;j++)<br /> {<br /> scanf("%d",&order[i][j]);<br /> }<br /> }<br /> for(int i=0;i<M;i++)<br /> {<br /> for(int j=0;j<K;j++)<br /> {<br /> scanf("%d",&storage[i][j]);<br /> }<br /> }<br /> for(int i=0;i<K;i++)<br /> {<br /> int sum1=0,sum2=0;<br /> for(int j=0;j<N;j++)<br /> {<br /> sum1+=order[j][i];<br /> }<br /> for(int j=0;j<M;j++)<br /> {<br /> sum2+=storage[j][i];<br /> }<br /> if(sum1>sum2)<br /> {<br /> no_ans=true;<br /> ans=-1;<br /> break;<br /> }<br /> }<br /> for(int i=0;i<K;i++)<br /> {<br /> memset(cost,0,sizeof(cost));<br /> for(int j=0;j<N;j++)<br /> {<br /> for(int k=0;k<M;k++)<br /> {<br /> scanf("%d",&cost[N+k][j]);<br /> cost[j][N+k]=-cost[N+k][j];<br /> }<br /> }<br /> if(no_ans) continue;<br /> else<br /> {<br /> memset(map,0,sizeof(map));<br /> for(int j=0;j<N;j++)<br /> map[j][N+M]=order[j][i];//构建汇点<br /> for(int j=0;j<M;j++)<br /> map[N+M+1][j+N]=storage[j][i];//构建源点<br /> for(int j=N;j<N+M;j++)<br /> for(int k=0;k<N;k++)<br /> map[j][k]=10;<br /> ans+=Min_Cost_Max_Flow(M+N+2,M+N+1,M+N);<br /> }<br /> }<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }<br />