链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2023

题意:

对于一个R行C列的正整数矩阵(1≤R,C≤20),设Ai为前i行所有元素之和,Bi为前i列所有元素之和。
已知R,C和数组A和B,找一个满足条件的矩阵。矩阵中的元素必须是1~20之间的正整数。输入保证有解。

分析:

首先根据Ai和Bi计算出第i行的元素之和Ai'和第i列的元素之和Bi'。
如果把矩阵里的每个数都减1,则每个Ai'会减少C,而每个Bi'会减少R。
这样一来,每个元素的范围变成了0~19,它的好处很快就能看到。
建立一个二分图,每行对应一个X结点,每列对应一个Y结点,然后增加源点s和汇点t。
对于每个结点Xi,从s到Xi连一条弧,容量为Ai'-C;从Yi到t连一条弧,容量为Bi'-R。
而对于每对结点(Xi,Yj),从Xi向Yj连一条弧,容量为19。
接下来求s-t的最大流,如果所有s出发和到达t的边都满载,说明问题有解,
结点Xi->Yj的流量就是格子(i,j)减1之后的值。

代码:

 #include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std; /// 结点下标从0开始,注意maxn
struct Dinic {
static const int maxn = + ;
static const int INF = 0x3f3f3f3f;
struct Edge {
int from, to, cap, flow;
}; int n, m, s, t; // 结点数,边数(包括反向弧),源点编号和汇点编号
vector<Edge> edges; // 边表。edges[e]和edges[e^1]互为反向弧
vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; // BFS使用
int d[maxn]; // 从起点到i的距离
int cur[maxn]; // 当前弧下标 void init(int n) {
this->n = n;
edges.clear();
for(int i = ; i < n; i++) G[i].clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back((Edge){from, to, cap, });
edges.push_back((Edge){to, from, , });
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool BFS() {
memset(vis, , sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = ;
d[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(!vis[e.to] && e.cap > e.flow) { // 只考虑残量网络中的弧
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[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[x]+ == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow))) > ) {
e.flow += f;
edges[G[x][i]^].flow -= f;
flow += f;
a -= f;
if(a == ) break;
}
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = ;
while(BFS()) {
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
vector<int> Mincut() { // 在Maxflow之后调用
vector<int> ans;
for(int i = ; i < edges.size(); i++) {
Edge& e = edges[i];
if(vis[e.from] && !vis[e.to] && e.cap > ) ans.push_back(i);
}
return ans;
}
}; const int UP = + ;
int id[UP][UP];
Dinic dc; int main() {
int T, R, C;
scanf("%d", &T);
for(int cases = ; cases <= T; cases++) {
scanf("%d%d", &R, &C);
dc.init(R+C+);
int start = R+C, finish = R+C+, last = ;
for(int v, i = ; i < R; i++) {
scanf("%d", &v);
dc.AddEdge(start, i, v - last - C);
last = v;
}
last = ;
for(int v, i = ; i < C; i++) {
scanf("%d", &v);
dc.AddEdge(R+i, finish, v - last - R);
last = v;
}
for(int r = ; r < R; r++) {
for(int c = ; c < C; c++) {
dc.AddEdge(r, R+c, );
id[r][c] = dc.edges.size() - ;
}
} dc.Maxflow(start, finish);
printf("Matrix %d\n", cases);
for(int r = ; r < R; r++) {
for(int c = ; c < C; c++) {
printf("%d ", dc.edges[id[r][c]].flow + );
}
printf("\n");
}
printf("\n");
}
return ;
}

最新文章

  1. 在Visual Studio 2012中使用VMSDK开发领域特定语言(一)
  2. Android开发-取消程序标题栏或自定义标题栏
  3. Principal Component Analysis(PCA) algorithm summary
  4. [数据结构] N皇后问题
  5. Caesar&#39;s Legions(三维dp)
  6. TCP建立连接的3次握手和关闭连接的4次挥手
  7. 印钞机 V1.0(量化选基总结)
  8. 用nginx缓存静态文件
  9. 如何设置PPT中的演讲者模式
  10. Python mac安装mysqlclient的一个bug
  11. 深度好文 | 在阿里做了5年技术Leader,我总结出了这些套路!
  12. ELK收集tomcat访问日志并存取mysql数据库案例
  13. sort 快排解决百万级的排序
  14. Hadoop基础-网络拓扑机架感知及其实现
  15. qrcodebox 面向移动设备的二维码弹出框
  16. Python并发讨论
  17. iPhone X 游戏闪退:NSUnknownKeyException
  18. kylin入门到实战:入门
  19. 一个很有用的树形控件----zTree
  20. Spring MVC起步

热门文章

  1. .Net程序员玩转Android系列之一~Java快速入门
  2. Bookstrap4 学习(一)
  3. invalid stream header: EFBFBDEF 问题解决
  4. C# WCF服务入门
  5. tp3.2开启允许跨域
  6. 排序算法lowb三人组-选择排序
  7. css样式的优先顺序
  8. Grunt实例
  9. js修改日期
  10. 参数化查询为什么能够防止SQL注入 (转)