UVA11082:Matrix Decompressing

题意:给定一个矩阵的前i行的和,以及前i列的和,求任意一个满足条件的矩阵,矩阵元素在[1,20]

矩阵行列<=20

题解:做一个二分图的模型,把行列拆开,然后设源点到行节点的容量就是该行所有元素的和,设汇点到列节点的容量就是该列所有元素的和

然后分别减去列数和行数,再把每个行节点和列节点之间连一条长度为19的边,这样的好处就是全部减了1,流的非负的,从而满足[1,20]

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define MAXN 220
#define INF 0x7f7f7f7f
using namespace std;
int n,m;
int a[MAXN],b[MAXN];
struct Edge{
int from,to,cap,flow;
Edge(int u=,int v=,int c=,int f=){
from=u,to=v,cap=c,flow=f;
}
};
struct Dinic{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[MAXN<<];
int b[MAXN<<];
int d[MAXN<<];
int cur[MAXN<<];
void init(int n,int s,int t){
this->n=n;
this->s=s,this->t=t;
edges.clear();
for(int i=;i<=n;i++){
G[i].clear();
}
}
void AddEdge(int x,int y,int cap){
edges.push_back(Edge(x,y,cap,));
edges.push_back(Edge(y,x,,));
m=edges.size();
G[x].push_back(m-);
G[y].push_back(m-);
}
bool BFS(){
memset(b,,sizeof(b));
queue<int> q;
d[s]=;
q.push(s);
b[s]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(e.cap>e.flow&&!b[e.to]){
d[e.to]=d[x]+;
q.push(e.to);
b[e.to]=;
}
}
}
return b[t];
}
int dfs(int x,int a){
if(x==t||!a)return a;
int flow=,f;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.to]==d[x]+&&(f=dfs(e.to,min(a,e.cap-e.flow)))>){
edges[G[x][i]].flow+=f;
edges[G[x][i]^].flow-=f;
flow+=f;
a-=f;
if(!a){
break;
}
}
}
return flow;
}
int Maxflow(){
int flow=;
while(BFS()){
memset(cur,,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
}D;
void init(){
scanf("%d%d",&n,&m);
D.init(n+m+,,n+m+);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<=m;i++){
scanf("%d",&b[i]);
}
for(int i=n;i>=;i--){
a[i]-=a[i-];
}
for(int i=m;i>=;i--){
b[i]-=b[i-];
}
for(int i=;i<=n;i++){
D.AddEdge(,i,a[i]-m);
}
for(int i=;i<=m;i++){
D.AddEdge(i+n,n+m+,b[i]-n);
}
for(int i=;i<=n;i++){
for(int j=n+;j<=n+m;j++){
D.AddEdge(i,j,);
}
}
}
int s[MAXN][MAXN];
int T;
void solve(){
D.Maxflow();
for(int i=;i<D.edges.size();i++){
Edge& e=D.edges[i];
// printf("%d->%d:c=%d f=%d\n",e.from,e.to,e.cap,e.flow);
if(<=e.from&&e.from<=n&&n+<=e.to&&e.to<=n+m){
s[e.from][e.to-n]=e.flow+;
}
}
for(int i=;i<=n;i++){
for(int j=;j<m;j++){
printf("%d ",s[i][j]);
}
printf("%d\n",s[i][m]);
}
printf("\n");
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%d",&T);
for(int i=;i<=T;i++){
printf("Matrix %d\n",i);
init();
solve();
}
return ;
}
上一篇:Linux apache的运行用户和用户组


下一篇:C里面的类型字节长度和范围