POJ 2516 最小费用流

依然最小费用最大流模板题

建边麻烦了些

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <deque>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
#define MAXM 3005
#define MAXN 300
using namespace std;struct Edge
{
    int y,c,w,ne;
}e[MAXM*];int all,be[MAXN],n,m,k,x,y,w,ans,Mincost,Maxflow,s,t,q[MAXM*];
int supply[MAXN][MAXN],need[MAXN][MAXN];
int pre[MAXN],dis[MAXN];
bool vis[MAXN];void init()
{
    all=;
    memset(be,-,sizeof(be));
}
void add(int x, int y, int c, int w)
{
    e[all].y=y;e[all].c=c;e[all].w=w;
    e[all].ne=be[x];
    be[x]=all++;    e[all].y=x;e[all].c=;e[all].w=-w;
    e[all].ne=be[y];
    be[y]=all++;
}bool spfa(int s, int t)
{
    queue<int> q;
    for(int i=; i<n+m+; i++)
    {
        dis[i]=INF;
        vis[i]=;
        pre[i]=-;
    }
    dis[s]=;
    vis[s]=;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        vis[u]=;
        q.pop();
        for(int i=be[u]; i!=-; i=e[i].ne)
        {
            int v=e[i].y;
            if(e[i].c && dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t]==-) return ;
    return ;
}void MincostMaxflow(int s, int t)
{
    Mincost=Maxflow=;
    while(spfa(s,t))
    {
        int minc=INF;
        for(int i=pre[t]; i!=-; i=pre[e[i^].y])
            if(minc>e[i].c) minc=e[i].c;
        for(int i=pre[t]; i!=-; i=pre[e[i^].y])
        {
            e[i].c-=minc;
            e[i^].c+=minc;
            Mincost+=e[i].w*minc;
        }
        Maxflow+=minc;
    }
}int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF && n && m && k)
    {        for(int i=; i<n; i++)
            for(int j=; j<k; j++)
            scanf("%d",&need[i][j]);
        for(int i=; i<m; i++)
            for(int j=; j<k; j++)
            scanf("%d",&supply[i][j]);        s=m+n;
        t=m+n+;
        bool flag=;
        ans=;
        for(int tk=; tk<k; tk++)
        {
            init();
            for(int i=; i<n; i++)
                for(int j=; j<m; j++)
                {
                    scanf("%d",&w);
                    add(j,i+m,INF,w);
                }
            if(flag)
            {
                for(int i=; i<m; i++)
                    add(s,i,supply[i][tk],);
                for(int i=; i<n; i++)
                    add(m+i,t,need[i][tk],);
                MincostMaxflow(s,t);                for(int i=be[t]; i!=-; i=e[i].ne)
                    if(e[i^].c>) flag=;
                if(flag) ans+=Mincost;
            }
        }
        if(!flag) printf("-1\n");
        else printf("%d\n",ans);
    }
    return ;
}