hdu - 4888 - Redraw Beautiful Drawings(最大流)
标签:blog http io os ar for on 2014 log
题意:给一个N行M列的数字矩阵的行和以及列和,每个元素的大小不超过K,问这样的矩阵是否存在,是否唯一,唯一则求出各个元素N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400), K(1 ≤ K ≤ 40)。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4888
——>>建图:
1)超级源S = 0,超级汇T = N + M + 1;
2)S到每个行和各连一条边,容量为该行行和;
3)每个行和到每个列和各连一条边,容量为K;
4)每个列和到 T 各连一条边,容量为该列列和。
一个行到所有列连边,为的是让该行分流多少给各个列,正是该行某列元素的大小。。
所以,如果 S 到 T 的最大流 == 所有元素的和,则说明有解。。
残量网络中的行列结点之间如果有长度 > 2 的环(自环长度为2,但无法调整流量),则说明这个环中的流量可以调整,使得达到最大流时该环上的流量不唯一,即矩阵不唯一。。
#include
#include
#include
#include
using std::min;
using std::queue;
const int MAXN = 400 * 2 + 10;
const int MAXM = 400 * 400 + 2 * MAXN;
const int INF = 0x3f3f3f3f;
struct EDGE
{
int to;
int cap;
int flow;
int nxt;
} edge[MAXM qu;
qu.push(S);
h[S] = 0;
while (!qu.empty())
{
int u = qu.front();
qu.pop();
for (int e = hed[u]; e != -1; e = edge[e].nxt)
{
int v = edge[e].to;
if (h[v] == -1 && edge[e].cap > edge[e].flow)
{
h[v] = h[u] + 1;
qu.push(v);
}
}
}
return h[T] != -1;
}
int Dfs(int u, int cap)
{
if (u == T || cap == 0) return cap;
int flow = 0, subFlow;
for (int e = cur[u]; e != -1; e = edge[e].nxt)
{
cur[u] = e;
int v = edge[e].to;
if (h[v] == h[u] + 1 && (subFlow = Dfs(v, min(cap, edge[e].cap - edge[e].flow))) > 0)
{
flow += subFlow;
edge[e].flow += subFlow;
edge[e ^ 1].flow -= subFlow;
cap -= subFlow;
if (cap == 0) break;
}
}
return flow;
}
int Dinic()
{
int maxFlow = 0;
while (Bfs())
{
memcpy(cur, hed, sizeof(hed));
maxFlow += Dfs(S, INF);
}
return maxFlow;
}
void Read()
{
int r, c;
int rsum = 0, csum = 0;
S = 0;
T = N + M + 1;
for (int i = 1; i = 1; --j)
{
AddEdge(i, j + N, K);
}
}
}
void CheckPossible()
{
if (impossible) return;
if (Dinic() != sum)
{
impossible = true;
}
}
bool vis[MAXN];
bool CheckCircle(int x, int f)
{
vis[x] = true;
for (int e = hed[x]; e != -1; e = edge[e].nxt)
{
if (edge[e].cap > edge[e].flow)
{
int v = edge[e].to;
if (v == f) continue;
if (vis[v]) return true;
else
{
if (CheckCircle(v, x)) return true;
}
}
}
vis[x] = false;
return false;
}
void CheckUnique()
{
if (impossible) return;
memset(vis, 0, sizeof(vis));
for (int i = 1; i
hdu - 4888 - Redraw Beautiful Drawings(最大流)
标签:blog http io os ar for on 2014 log
原文地址:http://blog.csdn.net/scnu_jiechao/article/details/40658221
评论