| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我也贴一个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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator