本文主要是介绍UVa11082 Matrix Decompressing - 最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2023
题意：知道矩阵的前i行之和，和前j列之和（任意i和j都可以）。求这个矩阵。每个格子中的元素必须在1~20之间。矩阵大小上限20*20。
解题思路：RT.经典构图【S->i,流量限制为第i行的和；j->T类似。对于每条(i,j)的实际流量则表示所构造出来的矩阵中(i,j)的大小
因为每个数都是必须在1~20间，所以我一开始就使其为1+ 0~19 直接跑最大流
p.s.题目说的是前i行、前j列的和！所以要稍微转化一下！！而没有智商的我以为是第i行、第j行，调了好久都不知道错在哪= =
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1100
#define maxm 30
#define INF 0x7fffffffstruct node
{int y,c,next,ot;
}a[maxn];int len,first[maxn];
int S,T,as[maxm][maxm],d[maxn];
int mx[maxm],my[maxm];
int mymin(int x,int y){return (x<y)?x:y;}
void ins(int x,int y,int c)
{len++;int k1=len;a[k1].y=y;a[k1].c=c;a[k1].next=first[x];first[x]=len;len++;int k2=len;a[k2].y=x;a[k2].c=0;a[k2].next=first[y];first[y]=len;a[k1].ot=k2;a[k2].ot=k1;
}
bool bfs()
{queue<int> q;memset(d,-1,sizeof(d));q.push(S);d[S]=0;while (!q.empty()){int x=q.front();q.pop();for (int k=first[x];k!=-1;k=a[k].next){int y=a[k].y;if (d[y]==-1 && a[k].c>0){d[y]=d[x]+1;q.push(y);}}}return d[T]!=-1;
}
int dfs(int x,int flow)
{if (x==T) return flow;int minf=0,p,i;for (i=first[x];i!=-1;i=a[i].next){int y=a[i].y;if (d[y]==d[x]+1 && a[i].c>0){p=mymin(a[i].c,flow-minf);p=dfs(y,p);minf+=p;a[i].c-=p;a[a[i].ot].c+=p;if (minf==flow) break;}}if (minf==0) d[x]=-1;return minf;
}
int dinic()
{int sum=0;while (bfs()) sum+=dfs(S,INF);return sum;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int tt,n,m,x,i,j,Case=0;scanf("%d",&tt);mx[0]=my[0]=0;while(tt--){scanf("%d%d",&n,&m);S=0;T=n+m+1;len=0;memset(first,-1,sizeof(first));for (i=1;i<=n;i++){scanf("%d",&mx[i]);ins(S,i,mx[i]-mx[i-1]-m);}for (i=1;i<=m;i++){scanf("%d",&my[i]);ins(i+n,T,my[i]-my[i-1]-n);}for (i=1;i<=n;i++)for (j=1;j<=m;j++){ins(i,j+n,19);as[i][j]=len;}printf("Matrix %d\n",++Case);int ls=dinic();for (i=1;i<=n;i++){for (j=1;j<=m;j++)printf("%d ",1+a[as[i][j]].c);printf("\n");}printf("\n");}return 0;
}
这篇关于UVa11082 Matrix Decompressing - 最大流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
