poj-2516-Minimum Cost-最小费用最大流

这道题目分别求每一商品的最小费用，然后加起来就可以了。

但是调试了很久，郁闷，好多地方写的不对。也许是自己没看模版的原因。

记住：

1，反向边初始化为0；

2，spfa的标记。

3，初始化。

[html]
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
    int u;
    int v;
    int next;
    bool friend operator < (node a, node b){
        return a.u< b.u;
    }
}edge[100001];
int head[1000010];
int 易做图(int n,int m){if(n<m) swap(n,m);return n%m==0?m:易做图(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/易做图(n,m)*m;}
int n,m,k;
int need[101][101];//第i个店主对物品j的需求；
int give[101][101];//第i个供货商对物品j的供货能力；
int fei[101][101][101];//i,j,k;第k个物品，供货商j对店主i的费用
int cost[501][501];
int p[1001];
int num=0;
void add(int l,int r,int v)
{
    edge[num].u=r;
    edge[num].v=v;
    edge[num].next=head[l];
    head[l]=num;
    num++;
}
int spfa()
{
    int visit[100001];
    int i,dist[10001];
    memset(visit,0,sizeof(visit));
    memset(p,-1,sizeof(p));
    queue<int>q;
    for(i=0;i<=n+m+1;i++)dist[i]=INF;
    dist[0]=0;
    q.push(0);
    visit[0]=1;
    while(!q.empty())
    {
        int e;
        e=q.front();
        q.pop();
        visit[e]=0;
        //printf("tan->%d\n",e);
        for(i=head[e];i!=-1;i=edge[i].next)
        {
            int r=edge[i].u;
           // printf("%d %d %d %d %d\n",e,r,dist[e],dist[r],edge[i].v);
            if(dist[r]>dist[e]+edge[i].v&&cost[e][r])
            {
                p[r]=e;
                dist[r]=dist[e]+edge[i].v;
                //printf("----p[%d]=%d\n",r,e);
                if(!visit[r])
                {
                    visit[r]=1;
                    q.push(r);
                  // printf("%d\n",r);
                }
            }
        }
        //visit[e]=1;

    }
    if (dist[n+m+1] == INF) return false;
    return true;
    //if(p[n+m+1]!=-1)return 1;
    //return 0;
}
void zeng()
{
   // puts("sf");
    int minl;
    minl=INF;
    int i;
    for(i=n+m+1;p[i]!=-1;i=p[i])
    {
        minl=min(minl,cost[p[i]][i]);
        //printf("p[%d]=%d\n",i,p[i]);
    }
   // printf("%d\n",minl);
    for(i=n+m+1;p[i]!=-1;i=p[i])
    {
        int j=p[i];
     //   printf("cost[%d][%d]=%d\n",j,i,cost[j][i]);
        cost[j][i]-=minl;
        cost[i][j]+=minl;
       // printf("cost[%d][%d]=%d\n",j,i,cost[j][i]);
    }
}
int main()
{
    int i,j,kk;
    while(scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
    {
        mem(cost,0);
        mem(head,-1);
        num=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=k;j++)
            {
                scanf("%d",&need[i][j]);
            }
        }
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=k;j++)
            {
                scanf("%d",&give[i][j]);
            }
        }
        for(kk=1;kk<=k;kk++)
        {
      &n

补充：软件开发 , C++ ,