Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我也贴一个

Posted by qq2308091457 at 2016-08-13 09:54:31 on Problem 2516
In Reply To:贴代码 Posted by:18357 at 2014-08-17 10:57:27
#include<iostream>
#include<cstdio>
#define INF 1000000000
#define N 500
using namespace std;
int ans,sum,num;
int shoper[N][N],shop[N][N],cost[N][N],n,m,k;
int D[N],head,root,path[N],visit[N],dis[N];
struct HAHA
{
	int cost,r;
}map[N][N];
void buildG(int x)
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&cost[i][j]);
	for(i=0;i<=n+m+1;i++)
		for(j=0;j<=n+m+1;j++)
			map[i][j].cost=map[i][j].r=0;
	for(i=1;i<=m;i++)
	{
		map[0][i].r=shop[i][x];
		map[0][i].cost=0;
	}
	sum=0;
	for(i=1;i<=n;i++)
	{
		map[m+i][n+m+1].r=shoper[i][x];
		sum+=shoper[i][x];
		map[m+i][n+m+1].cost=0;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			map[j][m+i].cost=cost[i][j];
			map[m+i][j].cost=cost[i][j]*-1;
			map[j][m+i].r=INF;
		}
}
void update()
{
	int i;
	for(i=0;i<=n+m+1;i++)
	{
		path[i]=i;
		visit[i]=0;
		dis[i]=INF;
	}
	D[0]=0;
	head=0;
	root=1;
	visit[0]=1;
	dis[0]=0;
}
bool SPFA()
{
	while(1)
	{
		int v=D[head];
		head++;
		visit[v]=0;
		int i;
		for(i=1;i<=n+m+1;i++)
			if(map[v][i].r&&dis[i]>dis[v]+map[v][i].cost)
			{
				path[i]=v;
				dis[i]=dis[v]+map[v][i].cost;
				if(!visit[i])
				{
					visit[i]=1;
					D[root]=i;
					root++;
				}
			}
		if(head==root)
			if(dis[n+m+1]==INF)
				return false;
			else
				return true;
	}
}
void upG()
{
	int i=n+m+1,j,min=INF;
	while(i!=0)
	{
		j=i;
		i=path[i];
		if(min>map[i][j].r)
			min=map[i][j].r;
	}
	num+=min;
	i=n+m+1;
	while(i!=0)
	{
		j=i;
		i=path[i];
		map[i][j].r-=min;
		map[j][i].r+=min;
		ans+=(map[i][j].cost*min);
	}
}
int main()
{
	while(1)
	{
		scanf("%d%d%d",&n,&m,&k);
		if(n==0&&m==0&&k==0)
			break;
		int i,j,flag=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=k;j++)
				scanf("%d",&shoper[i][j]);
		for(i=1;i<=m;i++)
			for(j=1;j<=k;j++)
				scanf("%d",&shop[i][j]);
		for(i=1;i<=k;i++)
		{
			buildG(i);
			num=0;
			while(1)
			{
				update();
				if(!SPFA())
					break;
				upG();
			}
			if(num!=sum)
				flag=1;
		}
		if(flag)
			printf("-1\n");
		else
			printf("%d\n",ans);
		ans=0;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator