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