首页 > 代码库 > POJ 2516 最小费用流

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 300using namespace std;struct Edge{    int y,c,w,ne;}e[MAXM*4];int all,be[MAXN],n,m,k,x,y,w,ans,Mincost,Maxflow,s,t,q[MAXM*4];int supply[MAXN][MAXN],need[MAXN][MAXN];int pre[MAXN],dis[MAXN];bool vis[MAXN];void init(){    all=0;    memset(be,-1,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=0;e[all].w=-w;    e[all].ne=be[y];    be[y]=all++;}bool spfa(int s, int t){    queue<int> q;    for(int i=0; i<n+m+2; i++)    {        dis[i]=INF;        vis[i]=0;        pre[i]=-1;    }    dis[s]=0;    vis[s]=1;    q.push(s);    while(!q.empty())    {        int u=q.front();        vis[u]=0;        q.pop();        for(int i=be[u]; i!=-1; 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]=1;                    q.push(v);                }            }        }    }    if(pre[t]==-1) return 0;    return 1;}void MincostMaxflow(int s, int t){    Mincost=Maxflow=0;    while(spfa(s,t))    {        int minc=INF;        for(int i=pre[t]; i!=-1; i=pre[e[i^1].y])            if(minc>e[i].c) minc=e[i].c;        for(int i=pre[t]; i!=-1; i=pre[e[i^1].y])        {            e[i].c-=minc;            e[i^1].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=0; i<n; i++)            for(int j=0; j<k; j++)            scanf("%d",&need[i][j]);        for(int i=0; i<m; i++)            for(int j=0; j<k; j++)            scanf("%d",&supply[i][j]);        s=m+n;        t=m+n+1;        bool flag=1;        ans=0;        for(int tk=0; tk<k; tk++)        {            init();            for(int i=0; i<n; i++)                for(int j=0; j<m; j++)                {                    scanf("%d",&w);                    add(j,i+m,INF,w);                }            if(flag)            {                for(int i=0; i<m; i++)                    add(s,i,supply[i][tk],0);                for(int i=0; i<n; i++)                    add(m+i,t,need[i][tk],0);                MincostMaxflow(s,t);                for(int i=be[t]; i!=-1; i=e[i].ne)                    if(e[i^1].c>0) flag=0;                if(flag) ans+=Mincost;            }        }        if(!flag) printf("-1\n");        else printf("%d\n",ans);    }    return 0;}
View Code