noj 2516 最小费用最大流.txt

ACM资料大集合

#include <cstdio>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

//NOJ 2516 最小费用最大流
#define NMAX 52
#define INFI 9999999

typedef struct node
{
	int cost[NMAX][NMAX];//cost[i][j],某种货物从第i个生产地到第j个销售地的花费
}node;


typedef struct arc
{
	int c;//容量
	int f;//流量
	int w;//权值
}arc;

arc net[NMAX*2][NMAX*2];
node pro[NMAX];
int fac[NMAX][NMAX];//fac[i][j]，第i个生产地的第j个货物的生产量
int shop[NMAX][NMAX];//shop[i][j],第i个销售地的第j个货物的销售量
int pre[NMAX*2],dis[NMAX*2],inc[NMAX*2];//最短增广路中的前驱、距离、增量
int src,end;//源点、汇点
int tot;//总流量
int n;//销售地数
int m;//生产地数
int cnt;//货品总数
int num;//图的总点数

void input()
{
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=cnt;j++)
			scanf("%d",&shop[i][j]);
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=cnt;j++)
			scanf("%d",&fac[i][j]);
	}
	for(i=1;i<=cnt;i++)
	{
		for(j=1;j<=n;j++)
		{
			for(k=1;k<=m;k++)
				scanf("%d",&pro[i].cost[k][j]);
		}
	}
}

void print()
{
	int i,j,k;
	printf("流图:\n");
	for(i=0;i<=num;i++)
	{
		for(j=0;j<=num;j++)
			printf("%3d ",net[i][j].c);
		cout<<endl;
	}
	cout<<endl;
	printf("权图:\n");
	for(i=0;i<=num;i++)
	{
		for(j=0;j<=num;j++)
			printf("%3d ",net[i][j].w);
		cout<<endl;
	}
	cout<<endl;
	system("pause");
}

void create(int x)//第x种货物
{
	int i,j,k;
	src=0;end=n+m+1;num=end;
//	printf("create (1) %d\n",x);
	for(i=0;i<=num;i++)
	{
		for(j=0;j<=num;j++)
		{
			net[i][j].c=0;
			net[i][j].f=0;
			net[i][j].w=INFI;
		}
	}

	for(i=1;i<=m;i++)
	{
		net[src][i].c=fac[i][x];
		net[src][i].w=0;
	}
	for(i=1;i<=n;i++)
	{
		net[i+m][end].c=shop[i][x];
		net[i+m][end].w=0;
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			net[i][j+m].c=INFI;
			net[i][j+m].w=pro[x].cost[i][j];
			net[j+m][i].w=-net[i][j+m].w;
		}
	}
//	print();
}

bool bellman_ford()
{
	int tmp,i,j;
	bool flag=true;
	for(i=0;i<=num;i++) 
	{
		dis[i]=INFI;
		inc[i]=INFI;
	}
//	memset(dis,INFI,sizeof(dis));
//	memset(inc,INFI,sizeof(inc));
	dis[src]=0;
//	printf("bellman_ford (1)\n");
//	printf("bellman_ford (2) end=%d inc[end]=%d\n",end,inc[end]);
	while(flag==true)
	{
		flag=false;
		for(i=0;i<=num;i++)
		{
			for(j=0;j<=num;j++)
			{
				if(net[i][j].f!=net[i][j].c &&  dis[j] > dis[i]+net[i][j].w)
				{//最短路可继续改进
					flag=true;
					dis[j]=dis[i]+net[i][j].w;
					pre[j]=i;
					if(net[i][j].c == 0) tmp=net[i][j].f; //反向弧
					else tmp=net[i][j].c-net[i][j].f;//正向弧
					if(tmp<inc[i]) inc[j]=tmp;
					else inc[j]=inc[i];
//				 printf("bellman_ford (3) i=%d inc[%d]=%d dis[%d]=%d\n",i,j,inc[j],j,dis[j]);
				}
			}
		}
//		printf("ciji_1\n");
	}
//	printf("bellman_ford (4) end=%d inc[end]=%d\n",end,inc[end]);
//	system("pause");
	if(dis[end]==INFI) return false;
	else return true;
}

void adjust()
{//改进流
	int now,t=inc[end];
	now=end;
	while(now!=src)
	{
		if(net[pre[now]][now].c==0) 
		{//反向弧
			net[pre[now]][now].f-=inc[end];
			net[now][pre[now]].f=net[pre[now]][now].f;
		}
		else
		{//正向弧
			net[pre[now]][now].f+=inc[end];
			net[now][pre[now]].f=net[pre[now]][now].f;
		}
		now=pre[now];
	}
}

int solve()
{
	int ans=0,i,j;
	while(bellman_ford()==true) adjust();//printf("siji_2\n");}

	for(i=1;i<=n;i++)
	{
//		printf("solve (1) i=%d net[i+m][end].f=%d c=%d\n",i,net[i+m][end].f,net[i+m][end].c);
		if(net[i+m][end].f!=net[i+m][end].c) return -1;
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(net[i][j+m].c>0)
			{
				ans+=net[i][j+m].w * net[i][j+m].f;
//				printf("solve (2) ans=%d\n",ans);
			}
		}
	}
	return ans;
}

int main()
{
	int i,tt,has;
	while(scanf("%d%d%d",&n,&m,&cnt)!=EOF && (n+m+cnt))
	{
		input();
		tot=0;
		has=1;
		for(i=1;i<=cnt;i++)
		{
//			printf("处理第%d种货物ing...\n",i);
			create(i);
			tt=solve();
			if(tt==-1) 
			{
				cout<<"-1"<<endl;
				has=0;
				break;
			}
			else
			{
				tot+=tt;
			}
		}
		if(has==1) cout<<tot<<endl;
	}
	return 0;
}