建模比较难想..
- #include<iostream>
- #include<deque>
- #include<vector>
- #include<cstring>
- #include<cmath>
- #define INF 2e9
- using namespace std;
- int T,ans;
- struct edge{
- int v,cap,reverse,cost;
- };
- vector<int> edges[1005];// 邻接表
- vector<edge> bian;// 所有的边都存在里面
- void addedge(int u,int v,int cost,int cap){//u 到 v 一条边, 再加一条反向边
- edge e;
- e.cap=cap;
- e.v=v;
- e.cost=cost;
- e.reverse=bian.size()+1;// 这条边的反边将建在这条边之后 (这条边建完后在 bian.size() 的位置)
- bian.push_back(e);
- edges[u].push_back(bian.size()-1);
- e.cap=0;
- e.v=u;
- e.cost=-cost;
- e.reverse=bian.size()-1;
- bian.push_back(e);
- edges[v].push_back(bian.size()-1);
- }
- int dist[1005],pre[1005];//pre[i]代表走的哪条边到的 i 点
- bool spfa(){
- for(int i=0;i<=T;i++) dist[i]=INF;
- for(int i=0;i<=T;i++) pre[i]=-1;
- deque<int> q;
- dist[0]=0; pre[0]=-1; q.push_back(0);
- while( !q.empty() ){
- int u = q.front(); q.pop_front();
- for(int i=0;i<edges[u].size();i++){// 所有以 u 为起点的边的边的索引
- edge &e = bian[ edges[u][i] ];
- int v=e.v;
- if( e.cap>0 && dist[u]+e.cost<dist[v] ){
- dist[v] = dist[u]+e.cost;
- pre[v]=edges[u][i];
- q.push_back(v);
- }
- }
- }
- if(dist[T]==INF) return false;
- return true;
- }
- int EK(){
- int max_flow=0;
- while( spfa() ){
- //cout<<"suc"<<endl;
- int u=T,minflow=INF;// 在终点位置
- while( u!=0 ){
- edge &e = bian[ pre[u] ];
- minflow=min(minflow,e.cap);
- u = bian[ e.reverse ].v;
- }
- ans+=minflow*dist[T];
- max_flow+=minflow;
- u=T;
- while( u!=0 ){
- edge &e = bian[ pre[u] ];
- e.cap-=minflow;
- bian[ e.reverse ].cap+=minflow;
- u = bian[ e.reverse ].v;
- }
- }
- return max_flow;
- }
- int order[55][55],supply[55][55];//order 是第 i 个商家对第 j 个物品的需求 supply 第 i 个 supply 对第 j 个物品的库存
- int main(){
- int n,m,k;
- while(1){
- cin>>n>>m>>k;
- if(n==0 && m==0 && k==0) break;
- ans=0;
- //supply:1-M shopkeeper:M+1 - M+N
- T = n+m+1;
- //k 个物品间是相互独立的, 所以等于跑 k 次费用流
- for(int i=1;i<=n;i++)
- for(int j=1;j<=k;j++) cin>>order[i][j];
- for(int i=1;i<=m;i++)
- for(int j=1;j<=k;j++) cin>>supply[i][j];
- bool flag=true;
- for(int k1=1;k1<=k;k1++){//k1 个商品
- bian.clear();
- for(int i=0;i<=T;i++) edges[i].clear();
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){// 第 j 个供应商给 i 商店供应 k 商品的代价
- int cost; cin>>cost;
- addedge(j,m+i,cost,INF);
- }
- }
- //supply 到 shop 解决了
- for(int i=1;i<=n;i++) addedge(m+i,T,0,order[i][k1]);//shop 到汇点
- for(int i=1;i<=m;i++) addedge(0,i,0,supply[i][k1]);
- int sum=0;
- for(int i=1;i<=n;i++) sum+=order[i][k1];
- if( EK()!=sum ) flag=false;
- }
- if( flag ) cout<<ans<<endl;
- else cout<<"-1"<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2740715.html