UVA11082 矩阵展开,最大流

Posted by Cww97 on 2016-08-18

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52236211
某题解
题意:

知道矩阵的前i行之和,和前j列之和(任意i和j都可以)。求这个矩阵。每个格子中的元素必须在1~20之间。矩阵大小上限20*20。

思路:

这么也想不到用网络流解决,这个模型很不错。假设这个矩阵的每一行是水管,每一列是水管,每行有出水口流到每一列,这样想比较好理解。然后每行的流量和每列的流量知道,就可以建图了。

建图过程,每行对应一个点,每列对应1个点,每行都可以流到每列,所以他们之间有边。我们得假设他们是如何流向的,不如设从行流向列,那么添加源点,流向每行;添加汇点,被每列汇流。容量怎么设?我们要让每行都满流就行了,那么行之和就是源点到该行的容量,同理汇点也如此。但是每行流向每列呢?注意每个格子的元素必须在1~20之间,所以把容量设为20,别让它流太多了。

注意到元素必须在1~20之间!!!那么这样增广路的话会出现有的完全0流怎么办?先将每个格子中的元素自减1,它的流下限总不会为负吧,计算完输出时再加回去不就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//UVA 11082     Matrix Decompressing
//by cww97
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N = 23 << 1 ;
int n,m,a[N],b[N],ans[N][N];

struct gragh{
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int s,t; //0=s,1~n行,n+1~n+m列,n+m+1=t
vector<Edge>edges;
vector< int>G[N]; //gragh
bool vis[N]; //use when bfs
int d[N],cur[N];//dist,now edge,use in dfs

inline void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
int top=edges.size();
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}

inline bool BFS(){
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);d[s]=0;vis[s]=1;
while (!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge &e=edges[G[x][i]];
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}

inline int DFS(const int& x,int a){
//printf("dfs:%d,%d\n",x,a);
if (x==t||a==0){return a;}
int flow = 0, f;
for (int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (d[x]+1!=d[e.to])continue;
if ((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue;
e.flow += f;
edges[G[x][i]^1].flow-=f;//反向边
flow+=f; a-=f;
if (a==0) break;
}
return flow;
}

inline int maxflow(){return Maxflow(s,t);}
inline int Maxflow(const int& s,const int& t){
int flow=0;
memset(ans,0,sizeof(ans));
while(BFS()){
memset(cur,0,sizeof(cur));
int f = DFS(s,INF);
flow += f ;
}
for (int i=0;i<edges.size();i++){
Edge e=edges[i];
ans[e.from][e.to-n]+=e.flow;
}
return flow;
}

inline void Init(){
s = 0, t = n+m+1;
edges.clear();
for (int i=0;i<=m+n+1;i++) G[i].clear() ;
for (int i=1;i<=n;i++) AddEdge( s ,i,a[i]) ;
for (int i=1;i<=m;i++) AddEdge(i+n,t,b[i]) ;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)AddEdge(i,j+n,19);
}
}g;
//=================cww97======================
int main(){
//freopen("fuck.in","r",stdin);
int T;
scanf("%d",&T);
for (int cas=1;cas<=T;cas++){
printf("Matrix %d\n",cas);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
for (int i=1;i<=m;i++)scanf("%d",&b[i]);
for (int i=n;i>=1;i--)a[i] -= a[i-1]+m ;
for (int i=m;i>=1;i--)b[i] -= b[i-1]+n ;
g.Init();
int flow = g.maxflow();
for (int i=1;i<=n;i++){
for (int j=1;j<m;j++)
printf("%d ",ans[i][j]+1);
printf("%d\n",ans[i][m]+1);
}
if (cas<T)puts("");
}
return 0;
}