正文
UVa 11082 Matrix Decompressing - 网络流
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
开始眨眼一看怎么也不像是网络流的一道题，再怎么看也觉得像是搜索。不过虽然这道题数据范围很小，但也不至于搜索也是可以随随便便就可以过的。（不过这道题应该是special judge，因为一题可以多解而且题目中然而并没有什么要求，所以说可以考虑思考一下这道题有木有什么"套路"之类的通法）
比如说有这么一组数据
原矩阵 输入
然后将每一行的和写在每一列对应的行上（很明显有问题）
然后调整，为了简便先每个向右挪个1（保障不会出现0什么之类的），接着就随便怎么移都可以，只要第一列满足且每一行的和也满足就行了
（应该发现了上图的"猫腻"吧！）
故技重施，是第二列满足
此时第三列应该也是满足的。
因此，这道题是不是贪心啊？如果您这么认为那么您可以去写一写，反正我是写不出来的，需要考虑的情况似乎还是有点多。不过可以找到代替贪心的东西——最大流。
源点直接连接每一行的第一个元素，这条弧的容量为这一行的和。每行相邻的两个元素间有一条弧，容量为这一行的和。除此之外，每一列再增加一个元素，这一列的每一个元素都连接这个点，容量为20。到这里，已经可以发现一些不对的地方，知道这个网络流是干什么的已经可以发现了。每一列流向这个"列汇点"的流量就代表矩阵这个位置的值，然而题目中的要求是1~20。如果照这样做的话，会变成0~20。于是可以将所有元素的值减少1（相应的列、行的和减少多少要清楚）。这条边的容量也改为19。"列汇点"也有一条弧到真正的汇点，容量为这一列的和。
这样跑一趟最大流算法。最大流为这个矩阵所有元素的和。所以每一行的和满足了，每一列的和也满足了。输出的时候加个1就行了。
Code (极其不简洁的代码)
/**
* uva
* Problem#11082
* Accepted
* Time:20ms
*/
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
typedef bool boolean;
#define INF 0xfffffff
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} template<typename T>class Matrix{
public:
T *p;
int lines;
int rows;
Matrix():p(NULL){ }
Matrix(int rows, int lines):lines(lines), rows(rows){
p = new T[(lines * rows)];
}
T* operator [](int pos){
return (p + pos * lines);
}
};
#define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) ///map template starts
typedef class Edge{
public:
int end;
int next;
int cap;
int flow;
Edge(const int end = , const int next = , const int cap = , const int flow = ):end(end), next(next), cap(cap), flow(flow){}
}Edge;
typedef class MapManager{
public:
int ce;
Edge *edge;
int *h;
MapManager(){}
MapManager(int points, int limit):ce(){
h = NULL, edge = NULL;
h = new int[(const int)(points + )];
edge = new Edge[(const int)(limit + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end, int cap, int flow){
edge[++ce] = Edge(end, h[from], cap, flow);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end, int cap){
addEdge(from, end, cap, );
addEdge(end, from, cap, cap);
}
Edge& operator [](int pos) {
return edge[pos];
}
void clear(){
delete[] h;
delete[] edge;
ce = ;
}
}MapManager;
#define m_begin(g, i) (g)->h[(i)]
#define m_end(g, i) (g)->edge[(i)].end
#define m_next(g, i) (g)->edge[(i)].next
#define m_cap(g, i) (g)->edge[(i)].cap
#define m_flow(g, i) (g)->edge[(i)].flow
///map template ends int r, c;
int *lines, *rows;
Matrix<int> hj;
MapManager *g; inline void init(){
readInteger(r);
readInteger(c);
lines = new int[(const int)(c + )];
rows = new int[(const int)(r + )];
hj = Matrix<int>(r + , c + );
for(int i = , last = , a; i <= r; i++){
readInteger(a);
rows[i] = a - last - c;
last = a;
}
for(int i = , last = , a; i <= c; i++){
readInteger(a);
lines[i] = a - last - r;
last = a;
}
} int s, t, sizee; //源，汇，点数 inline int iom(int x, int y){ return (x - ) * c + y; } inline void build(){
s = , t = r * c + c + , sizee = t + ;
g = new MapManager(sizee, sizee * + );
for(int i = ; i < r; i++)
g->addDoubleEdge(s, i * c + , rows[i + ]);
for(int i = ; i <= c; i++)
g->addDoubleEdge(r * c + i, t, lines[i]);
for(int i = ; i <= r; i++){
for(int j = ; j <= c; j++){
if(j < c)
g->addDoubleEdge(iom(i, j), iom(i, j + ), rows[i]);
g->addDoubleEdge(iom(i, j), r * c + j, );
hj[i][j] = g->ce - ;
}
}
} int* divs;
boolean* visited;
queue<int> que; inline boolean getDivs(){
memset(visited, false, sizeof(boolean) * sizee);
que.push(s);
divs[s] = ;
visited[s] = true;
while(!que.empty()){
int e = que.front();
que.pop();
for(int i = m_begin(g, e); i != ; i = m_next(g, i)){
int& eu = m_end(g, i);
if(!visited[eu] && (*g)[i].cap > (*g)[i].flow){
visited[eu] = true;
divs[eu] = divs[e] + ;
que.push(eu);
}
}
}
return visited[t];
} int blockedflow(int node, int minf){
if(node == t || minf == ) return minf;
int f, flow = ;
for(int i = m_begin(g, node); i != ; i = m_next(g, i)){
int& e = m_end(g, i);
if(divs[e] == divs[node] + && (f = (blockedflow(e, min(minf, (*g)[i].cap - (*g)[i].flow)))) > ){
flow += f;
(*g)[i].flow += f;
(*g)[(i & ) ? (i + ) : (i - )].flow -= f;
minf -= f;
if(minf == ) break;
}
}
return flow;
} inline void maxflow(){
while(getDivs()){
blockedflow(, INF);
}
} inline void solve(){
visited = new boolean[sizee];
divs = new int[sizee];
maxflow();
for(int i = ; i <= r; i++){
for(int j = ; j <= c; j++){
printf("%d ", (*g)[hj[i][j]].flow + );
}
putchar('\n');
}
} inline void clearAll(){
delete[] visited;
delete[] divs;
delete[] lines;
delete[] rows;
delete[] hj.p;
delete[] g;
} int kase;
int main(){
readInteger(kase);
for(int k = ; k <= kase; k++){
init();
printf("Matrix %d\n", k);
build();
solve();
putchar('\n');
clearAll();
}
return ;
}
