[题解]UVa11082MatrixDecompressing

作者：手机用户2502887763 | 来源：互联网 | 2023-05-17 20:54

开始眨眼一看怎么也不像是网络流的一道题，再怎么看也觉得像是搜索。不过虽然这道题数据范围很小，但也不至于搜索也是可以随随便便就可以过的。（不过这道题应该是specialjudge，因

技术分享

　　开始眨眼一看怎么也不像是网络流的一道题，再怎么看也觉得像是搜索。不过虽然这道题数据范围很小，但也不至于搜索也是可以随随便便就可以过的。（不过这道题应该是special judge，因为一题可以多解而且题目中然而并没有什么要求，所以说可以考虑思考一下这道题有木有什么"套路"之类的通法）

　　比如说有这么一组数据

　　然后将每一行的和写在每一列对应的行上（很明显有问题）

6 0 0
19 0 0
20 0 0

　　然后调整，为了简便先每个向右挪个1（保障不会出现0什么之类的），接着就随便怎么移都可以，只要第一列满足且每一行的和也满足就行了

1 5 0
1 18 0
12 8 0

　　（应该发现了上图的"猫腻"吧！）

　　故技重施，是第二列满足

1 1 4
1 6 13
12 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
  8 #include
  9 #include
 10 #include
 11 #include
 12 #include
 13 #include
 14 #include
 15 #include
 16 #include<set>
 17 #include
 18 #include
 19 #include
 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
 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 templateclass 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 )
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

推荐阅读

get
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
go
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
get
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
js
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
get
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
get
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
get
Hibernate基础映射

在说Hibernate映射前，我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象，以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]

蜡笔小新 2023-12-14 10:57:47
int
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
get
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
js
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
js
指针的引用以及在什么情况下使用指针的引用

本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址，通过指针可以修改指针所指的变量的值。然而，如果想要修改指针的指向，就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法，并思考了在修改指针的指向后，取指针的输出结果。 ... [详细]

蜡笔小新 2023-12-13 12:54:29
get
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
express
用SQL语句怎么把已存在的列加上IDENTITY(1,1)属性

ALTERTABLE通过更改、添加、除去列和约束，或者通过启用或禁用约束和触发器来更改表的定义。语法ALTERTABLEtable{[ALTERCOLUMNcolu ... [详细]

蜡笔小新 2023-12-13 09:49:28
get
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
get
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新 2023-12-12 17:48:18

手机用户2502887763

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章

[题解]UVa11082MatrixDecompressing

Code(极其不简洁的代码)

Code_{(极其不简洁的代码)}