首页 > 代码库 > [题解]UVa 11082 Matrix Decompressing
[题解]UVa 11082 Matrix Decompressing
开始眨眼一看怎么也不像是网络流的一道题，再怎么看也觉得像是搜索。不过虽然这道题数据范围很小，但也不至于搜索也是可以随随便便就可以过的。（不过这道题应该是special judge，因为一题可以多解而且题目中然而并没有什么要求，所以说可以考虑思考一下这道题有木有什么"套路"之类的通法）
比如说有这么一组数据
原矩阵1 2 34 7 89 5 6输入3 36 25 4514 28 45
然后将每一行的和写在每一列对应的行上（很明显有问题）
6 0 019 0 020 0 0
然后调整，为了简便先每个向右挪个1（保障不会出现0什么之类的），接着就随便怎么移都可以，只要第一列满足且每一行的和也满足就行了
1 5 01 18 012 8 0
（应该发现了上图的"猫腻"吧！）
故技重施，是第二列满足
1 1 41 6 1312 7 1
此时第三列应该也是满足的。
因此，这道题是不是贪心啊？如果您这么认为那么您可以去写一写，反正我是写不出来的，需要考虑的情况似乎还是有点多。不过可以找到代替贪心的东西——最大流。
源点直接连接每一行的第一个元素，这条弧的容量为这一行的和。每行相邻的两个元素间有一条弧，容量为这一行的和。除此之外，每一列再增加一个元素，这一列的每一个元素都连接这个点，容量为20。到这里，已经可以发现一些不对的地方，知道这个网络流是干什么的已经可以发现了。每一列流向这个"列汇点"的流量就代表矩阵这个位置的值，然而题目中的要求是1~20。如果照这样做的话，会变成0~20。于是可以将所有元素的值减少1（相应的列、行的和减少多少要清楚）。这条边的容量也改为19。"列汇点"也有一条弧到真正的汇点，容量为这一列的和。
这样跑一趟最大流算法。最大流为这个矩阵所有元素的和。所以每一行的和满足了，每一列的和也满足了。输出的时候加个1就行了。
Code(极其不简洁的代码)
1 /** 2 * uva 3 * Problem#11082 4 * Accepted 5 * Time:20ms 6 */ 7 #include<iostream> 8 #include<cstdio> 9 #include<cctype> 10 #include<cstring> 11 #include<cstdlib> 12 #include<fstream> 13 #include<sstream> 14 #include<algorithm> 15 #include<map> 16 #include<set> 17 #include<queue> 18 #include<vector> 19 #include<stack> 20 using namespace std; 21 typedef bool boolean; 22 #define INF 0xfffffff 23 #define smin(a, b) a = min(a, b) 24 #define smax(a, b) a = max(a, b) 25 template<typename T> 26 inline void readInteger(T& u){ 27 char x; 28 int aFlag = 1; 29 while(!isdigit((x = getchar())) && x != ‘-‘); 30 if(x == ‘-‘){ 31 x = getchar(); 32 aFlag = -1; 33 } 34 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 35 ungetc(x, stdin); 36 u *= aFlag; 37 } 38 39 template<typename T>class Matrix{ 40 public: 41 T *p; 42 int lines; 43 int rows; 44 Matrix():p(NULL){ } 45 Matrix(int rows, int lines):lines(lines), rows(rows){ 46 p = new T[(lines * rows)]; 47 } 48 T* operator [](int pos){ 49 return (p + pos * lines); 50 } 51 }; 52 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) 53 54 ///map template starts 55 typedef class Edge{ 56 public: 57 int end; 58 int next; 59 int cap; 60 int flow; 61 Edge(const int end = 0, const int next = 0, const int cap = 0, const int flow = 0):end(end), next(next), cap(cap), flow(flow){} 62 }Edge; 63 typedef class MapManager{ 64 public: 65 int ce; 66 Edge *edge; 67 int *h; 68 MapManager(){} 69 MapManager(int points, int limit):ce(0){ 70 h = NULL, edge = NULL; 71 h = new int[(const int)(points + 1)]; 72 edge = new Edge[(const int)(limit + 1)]; 73 memset(h, 0, sizeof(int) * (points + 1)); 74 } 75 inline void addEdge(int from, int end, int cap, int flow){ 76 edge[++ce] = Edge(end, h[from], cap, flow); 77 h[from] = ce; 78 } 79 inline void addDoubleEdge(int from, int end, int cap){ 80 addEdge(from, end, cap, 0); 81 addEdge(end, from, cap, cap); 82 } 83 Edge& operator [](int pos) { 84 return edge[pos]; 85 } 86 void clear(){ 87 delete[] h; 88 delete[] edge; 89 ce = 0; 90 } 91 }MapManager; 92 #define m_begin(g, i) (g)->h[(i)] 93 #define m_end(g, i) (g)->edge[(i)].end 94 #define m_next(g, i) (g)->edge[(i)].next 95 #define m_cap(g, i) (g)->edge[(i)].cap 96 #define m_flow(g, i) (g)->edge[(i)].flow 97 ///map template ends 98 99 int r, c;100 int *lines, *rows;101 Matrix<int> hj;102 MapManager *g;103 104 inline void init(){105 readInteger(r);106 readInteger(c);107 lines = new int[(const int)(c + 1)];108 rows = new int[(const int)(r + 1)];109 hj = Matrix<int>(r + 1, c + 1);110 for(int i = 1, last = 0, a; i <= r; i++){111 readInteger(a);112 rows[i] = a - last - c;113 last = a;114 }115 for(int i = 1, last = 0, a; i <= c; i++){116 readInteger(a);117 lines[i] = a - last - r;118 last = a;119 }120 }121 122 int s, t, sizee; //源，汇，点数 123 124 inline int iom(int x, int y){ return (x - 1) * c + y; }125 126 inline void build(){127 s = 0, t = r * c + c + 1, sizee = t + 1;128 g = new MapManager(sizee, sizee * 4 + 1);129 for(int i = 0; i < r; i++)130 g->addDoubleEdge(s, i * c + 1, rows[i + 1]);131 for(int i = 1; i <= c; i++)132 g->addDoubleEdge(r * c + i, t, lines[i]);133 for(int i = 1; i <= r; i++){134 for(int j = 1; j <= c; j++){135 if(j < c)136 g->addDoubleEdge(iom(i, j), iom(i, j + 1), rows[i]);137 g->addDoubleEdge(iom(i, j), r * c + j, 19);138 hj[i][j] = g->ce - 1;139 }140 }141 }142 143 int* divs;144 boolean* visited;145 queue<int> que;146 147 inline boolean getDivs(){148 memset(visited, false, sizeof(boolean) * sizee);149 que.push(s);150 divs[s] = 0;151 visited[s] = true;152 while(!que.empty()){153 int e = que.front();154 que.pop();155 for(int i = m_begin(g, e); i != 0; i = m_next(g, i)){156 int& eu = m_end(g, i);157 if(!visited[eu] && (*g)[i].cap > (*g)[i].flow){158 visited[eu] = true;159 divs[eu] = divs[e] + 1;160 que.push(eu);161 }162 }163 }164 return visited[t];165 }166 167 int blockedflow(int node, int minf){168 if(node == t || minf == 0) return minf;169 int f, flow = 0;170 for(int i = m_begin(g, node); i != 0; i = m_next(g, i)){171 int& e = m_end(g, i);172 if(divs[e] == divs[node] + 1 && (f = (blockedflow(e, min(minf, (*g)[i].cap - (*g)[i].flow)))) > 0){173 flow += f;174 (*g)[i].flow += f;175 (*g)[(i & 1) ? (i + 1) : (i - 1)].flow -= f;176 minf -= f;177 if(minf == 0) break; 178 }179 }180 return flow;181 }182 183 inline void maxflow(){184 while(getDivs()){185 blockedflow(0, INF);186 }187 }188 189 inline void solve(){190 visited = new boolean[sizee];191 divs = new int[sizee];192 maxflow(); 193 for(int i = 1; i <= r; i++){194 for(int j = 1; j <= c; j++){195 printf("%d ", (*g)[hj[i][j]].flow + 1);196 }197 putchar(‘\n‘);198 }199 }200 201 inline void clearAll(){202 delete[] visited;203 delete[] divs;204 delete[] lines;205 delete[] rows;206 delete[] hj.p;207 delete[] g;208 }209 210 int kase;211 int main(){212 readInteger(kase);213 for(int k = 1; k <= kase; k++){214 init();215 printf("Matrix %d\n", k);216 build();217 solve();218 putchar(‘\n‘);219 clearAll();220 }221 return 0;222 }
[题解]UVa 11082 Matrix Decompressing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。