POJ2516 Minimum Cost（最小费用最大流）

一开始我把每个店主都拆成k个点，然后建图。。然后TLE。。

看题解= =哦，愚钝了，k个商品是独立的，可以分别跑k次最小费用最大流，结果就是k次总和。。

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define INF (1<<30)

 #define MAXN 111

 #define MAXM 111*111*2

 struct Edge{

     int u,v,cap,cost,next;

 }edge[MAXM];

 int head[MAXN];

 int NV,NE,vs,vt;

 void addEdge(int u,int v,int cap,int cost){

     edge[NE].u=u; edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;

     edge[NE].next=head[u]; head[u]=NE++;

     edge[NE].u=v; edge[NE].v=u; edge[NE].cap=; edge[NE].cost=-cost;

     edge[NE].next=head[v]; head[v]=NE++;

 }

 bool vis[MAXN];

 int d[MAXN],pre[MAXN];

 bool SPFA(){

     for(int i=;i<NV;++i){

         vis[i]=;

         d[i]=INF;

     }

     vis[vs]=;

     d[vs]=;

     queue<int> que;

     que.push(vs);

     while(!que.empty()){

         int u=que.front(); que.pop();

         for(int i=head[u]; i!=-; i=edge[i].next){

             int v=edge[i].v;

             if(edge[i].cap && d[v]>d[u]+edge[i].cost){

                 d[v]=d[u]+edge[i].cost;

                 pre[v]=i;

                 if(!vis[v]){

                     vis[v]=;

                     que.push(v);

                 }

             }

         }

         vis[u]=;

     }

     return d[vt]!=INF;

 }

 int MCMF(){

     int res=;

     while(SPFA()){

         int flow=INF,cost=;

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             flow=min(flow,edge[pre[u]].cap);

         }

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             edge[pre[u]].cap-=flow;

             edge[pre[u]^].cap+=flow;

             cost+=flow*edge[pre[u]].cost;

         }

         res+=cost;

     }

     return res;

 }

 int n,m,k,mat[][][],to[][],from[][];

 bool isOK(int *need,int *supply){

     for(int i=; i<k; ++i) if(need[i]>supply[i]) return ;

     return ;

 }

 int main(){

     int a;

     while(~scanf("%d%d%d",&n,&m,&k) && (n||m||k)){

         int sum=;

         int supply[]={},need[]={};

         for(int i=; i<n; ++i){

             for(int j=; j<k; ++j){

                 scanf("%d",&to[i][j]);

                 need[j]+=to[i][j];

             }

         }

         for(int i=; i<m; ++i){

             for(int j=; j<k; ++j){

                 scanf("%d",&from[i][j]);

                 supply[j]+=from[i][j];

             }

         }

         for(int z=; z<k; ++z){

             for(int x=; x<n; ++x){

                 for(int y=; y<m; ++y) scanf("%d",&mat[z][x][y]);

             }

         }

         if(!isOK(need,supply)){

             puts("-1");

             continue;

         }

         vs=n+m; vt=vs+; NV=n+m+;

         int res=;

         for(int good=; good<k; ++good){

             NE=;

             memset(head,-,sizeof(head));

             for(int i=; i<m; ++i) addEdge(vs,i,from[i][good],);

             for(int i=; i<n; ++i) addEdge(i+m,vt,to[i][good],);

             for(int i=; i<n; ++i){

                 for(int j=; j<m; ++j) addEdge(j,i+m,INF,mat[good][i][j]);

             }

             res+=MCMF();

         }

         printf("%d\n",res);

     }

     return ;

 }