hdu - 4888 - Redraw Beautiful Drawings（最大流）
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-11-07 08:56:27 閱讀次數(shù)：2713次
題意：給1個(gè)N行M列的數(shù)字矩陣的行和和列和，每一個(gè)元素的大小不超過(guò)K，問(wèn)這樣的矩陣是不是存在，是不是唯1，唯1則求出各個(gè)元素N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400), K(1 ≤ K ≤ 40)。
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4888
――>>建圖：
1）超級(jí)源S = 0，超級(jí)匯T = N + M + 1；
2）S到每一個(gè)行和各連1條邊，容量為該行行和；
3）每一個(gè)行和到每一個(gè)列和各連1條邊，容量為K；
4）每一個(gè)列和到 T 各連1條邊，容量為該列列和。
1個(gè)行到所有列連邊，為的是讓該行分流多少給各個(gè)列，正是該行某列元素的大小。。
所以，如果 S 到 T 的最大流 == 所有元素的和，則說(shuō)明有解。。
殘量網(wǎng)絡(luò)中的行列結(jié)點(diǎn)之間如果有長(zhǎng)度 > 2 的環(huán)（自環(huán)長(zhǎng)度為2，但沒(méi)法調(diào)劑流量），則說(shuō)明這個(gè)環(huán)中的流量可以調(diào)劑，使得到達(dá)最大流時(shí)該環(huán)上的流量不唯1，即矩陣不唯1。。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
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 << 1];
int N, M, K;
int sum;
int S, T;
int hed[MAXN], ecnt;
int cur[MAXN], h[MAXN];
bool impossible, bUnique;
void Init()
{
impossible = false;
bUnique = true;
ecnt = 0;
memset(hed, ⑴, sizeof(hed));
}
void AddEdge(int u, int v, int cap)
{
edge[ecnt].to = v;
edge[ecnt].cap = cap;
edge[ecnt].flow = 0;
edge[ecnt].nxt = hed[u];
hed[u] = ecnt++;
edge[ecnt].to = u;
edge[ecnt].cap = 0;
edge[ecnt].flow = 0;
edge[ecnt].nxt = hed[v];
hed[v] = ecnt++;
}
bool Bfs()
{
memset(h, ⑴, sizeof(h));
queue<int> qu;
qu.push(S);
h[S] = 0;
while (!qu.empty())
{
int u = qu.front();
qu.pop();
for (int e = hed[u]; e != ⑴; e = edge[e].nxt)
{
int v = edge[e].to;
if (h[v] == ⑴ && edge[e].cap > edge[e].flow)
{
h[v] = h[u] + 1;
qu.push(v);
}
}
}
return h[T] != ⑴;
}
int Dfs(int u, int cap)
{
if (u == T || cap == 0) return cap;
int flow = 0, subFlow;
for (int e = cur[u]; e != ⑴; 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 <= N; ++i)
{
scanf("%d", &r);
rsum += r;
AddEdge(S, i, r);
}
for (int i = 1; i <= M; ++i)
{
scanf("%d", &c);
csum += c;
AddEdge(i + N, T, c);
}
if (rsum != csum)
{
impossible = true;
return;
}
sum = rsum;
for (int i = 1; i <= N; ++i)
{
for (int j = M; j >= 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 != ⑴; 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 <= N; ++i)
{
if (CheckCircle(i, ⑴))
{
bUnique = false;
return;
}
}
}
void Output()
{
if (impossible)
{
puts("Impossible");
}
else if (!bUnique)
{
puts("Not Unique");
}
else
{
puts("Unique");
for (int i = 1; i <= N; ++i)
{
for (int e = hed[i], j = 1; e != ⑴ && j <= M; e = edge[e].nxt, ++j)
{
printf("%d", edge[e].flow);
if (j < M)
{
printf(" ");
}
}
puts("");
}
}
}
int main()
{
while (scanf("%d%d%d", &N, &M, &K) == 3)
{
Init();
Read();
CheckPossible();
CheckUnique();
Output();
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
