UVA 11082 Matrix Decompressing

xiaoxiao2021-02-28  33

#include<bits/stdc++.h> using namespace std; int r,c,a[30],b[30],pre[50],h[50][50]; bool vis[50]; int bfs(int s,int t){ int i,p; memset(vis,0,sizeof(vis)); queue<int>q;q.push(s); pre[s]=s;vis[s]=1; while(q.empty()==0){ p=q.front(); q.pop(); for(i=1;i<=r+c+2;i++) if(h[p][i]>0&&vis[i]==0){ pre[i]=p; vis[i]=1; if(i==t)return 1; q.push(i); } }; return 0; } void EK(int s,int t){ int i,d; while(bfs(s,t)){ d=1e9; for(i=t;i!=s;i=pre[i]) d=min(d,h[pre[i]][i]); for(i=t;i!=s;i=pre[i]){ h[pre[i]][i]-=d; h[i][pre[i]]+=d; } } } int main(){ int k,i,j,kase; scanf("%d",&kase); for(k=1;k<=kase;k++){ memset(h,0,sizeof(h)); scanf("%d%d",&r,&c); for(i=1;i<=r;i++) scanf("%d",&a[i]); for(i=1;i<=c;i++) scanf("%d",&b[i]); for(i=r;i>=1;i--) a[i]-=a[i-1]; for(i=c;i>=1;i--) b[i]-=b[i-1]; for(i=1;i<=r;i++) h[1][i+1]=a[i]-c; for(i=1;i<=c;i++) h[i+r+1][r+c+2]=b[i]-r; for(i=2;i<=r+1;i++) for(j=r+2;j<=r+c+1;j++) h[i][j]=19; EK(1,r+c+2); printf("Matrix %d\n",k); for(i=2;i<=r+1;i++){ for(j=r+2;j<=r+c+1;j++) printf("%d ",20-h[i][j]); printf("\n"); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2612992.html

最新回复(0)