Poj 2112[最大ストリーム][二分図の多重整合]
この問題に関連する知識点は比較的に多い:最短パス、二分検索、二分図の多重マッチング、最大ストリーム問題.
この問題には3つの解法がある.
1.図を再構築し,多重マッチングの点を複数の点に分割して二分図の最大マッチングを解く
2.ダイレクトデマルチプレクシング(二分図の最大マッチングアルゴリズムの1次元配列を2次元配列に変更)
3.最大流に変換する(始点sと終点tを追加し、図を再構築する):sから牛までの辺権は1であり、各搾乳器からtまでの辺権はmである.
3つの方法でコードを書きましたが、提出時間はそれぞれ:
1. 219MS 2. 79MS 3. 110MS
方法2と方法1の原理は同じだと思いますが、1つの2次元配列match[]]でマークすることは、複数のマッチング可能な点を複数の単一マッチングに分裂させた点に相当すると思いますが、上記の時間説明方法2の効率は方法1よりずっと高く、よく考えてみると、方法2は確かに多くの不要な遍歴を節約することができ、ここでは時間を節約することができます.
方法3については、discussでは最大ストリームでこの問題を解く効率が非常に低く、1000+MSに達すると言われていますが、Improved-SAPアルゴリズムを使ったのではないでしょうか.
メソッド1コード:
この問題には3つの解法がある.
1.図を再構築し,多重マッチングの点を複数の点に分割して二分図の最大マッチングを解く
2.ダイレクトデマルチプレクシング(二分図の最大マッチングアルゴリズムの1次元配列を2次元配列に変更)
3.最大流に変換する(始点sと終点tを追加し、図を再構築する):sから牛までの辺権は1であり、各搾乳器からtまでの辺権はmである.
3つの方法でコードを書きましたが、提出時間はそれぞれ:
1. 219MS 2. 79MS 3. 110MS
方法2と方法1の原理は同じだと思いますが、1つの2次元配列match[]]でマークすることは、複数のマッチング可能な点を複数の単一マッチングに分裂させた点に相当すると思いますが、上記の時間説明方法2の効率は方法1よりずっと高く、よく考えてみると、方法2は確かに多くの不要な遍歴を節約することができ、ここでは時間を節約することができます.
方法3については、discussでは最大ストリームでこの問題を解く効率が非常に低く、1000+MSに達すると言われていますが、Improved-SAPアルゴリズムを使ったのではないでしょうか.
メソッド1コード:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int MAXK = 30 + 1;
const int MAXC = 200 + 1;
const int MAXM = 15 + 1;
const int INF = 100000000;
using namespace std;
int k, c, m;
int map[MAXK+MAXC][MAXK+MAXC];
bool path[MAXC][MAXK*MAXM];
int match[MAXK*MAXM];
bool vst[MAXK*MAXM];
/* m ， <=tmp */
void buildGraph(int tmp)
{
memset(path, false, sizeof(path));
for (int i=1; i<=c; i++)
for (int j=1; j<=k; j++)
if (map[k+i][j] <= tmp)
{
for (int t=1; t<=m; t++)
{
path[i][(j-1)*m+t] = true;
}
}
}
bool DFS(int i)
{
for (int j=1; j<=k*m; j++)
{
if (path[i][j] && !vst[j])
{
vst[j] = true;
if (match[j] == -1 || DFS(match[j]))
{
match[j] = i;
return true;
}
}
}
return false;
}
/* ， ， true, false */
bool maxMatch()
{
memset(match, -1, sizeof(match));
for (int i=1; i<=c; i++)
{
memset(vst, false, sizeof(vst));
if (!DFS(i))
return false;
}
return true;
}
/* ， */
void solve()
{
int low = 1, high = 200*(k+c), mid;
while (low < high)
{
mid = (low + high)/2;
buildGraph(mid);
maxMatch() == true ? high = mid : low = mid+1;
}
printf("%d
", low);
}
void floyd()
{
int i, j, h, t = k+c;
for (h=1; h<=t; h++)
for (i=1; i<=t; i++)
for (j=1; j<=t; j++)
if (map[i][j] > map[i][h]+map[h][j])
map[i][j] = map[i][h]+map[h][j];
}
int main()
{
scanf("%d %d %d", &k, &c, &m);
for (int i=1; i<=k+c; i++)
for (int j=1; j<=k+c; j++)
{
scanf("%d", &map[i][j]);
if (map[i][j] == 0)
map[i][j] = INF;
}
floyd();
solve();
}bool path[MAXC][MAXK];
int match[MAXK][MAXM];
bool vst[MAXK];
/* <=tmp */
void buildGraph(int tmp)
{
memset(path, false, sizeof(path));
for (int i=1; i<=c; i++)
for (int j=1; j<=k; j++)
if (map[k+i][j] <= tmp)
{
path[i][j] = true;
}
}
/* ，match[] */
bool DFS(int i)
{
for (int j=1; j<=k; j++)
{
if (path[i][j] && !vst[j])
{
vst[j] = true;
if (match[j][0] < m)
{
match[j][++match[j][0]] = i;
return true;
}
for (int t=1; t<=m; t++)
{
if (DFS(match[j][t]))
{
match[j][t] = i;
return true;
}
}
}
}
return false;
}
/* ， ， true, false */
bool maxMatch()
{
memset(match, 0, sizeof(match));
for (int i=1; i<=c; i++)
{
memset(vst, false, sizeof(vst));
if (!DFS(i))
return false;
}
return true;
}#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int MAXK = 30 + 1;
const int MAXC = 200 + 1;
const int MAXM = 15 + 1;
const int MAXV = 300 + 1;
const int MAXE = 20000 + 1;
const int INF = 100000000;
using namespace std;
struct Edge
{
int v, cap, flow;
Edge *next;
Edge *rev;
} edge[MAXE];
Edge *node[MAXV];
int nE;
int k, c, m;
int map[MAXK+MAXC][MAXK+MAXC];
inline void addEdge(int u, int v, int w)
{
edge[nE].v = v;
edge[nE].cap = w;
edge[nE].next = node[u];
node[u] = &edge[nE++];
}
inline void addRevEdge(int u, int v, int w)
{
addEdge(u, v, w);
addEdge(v, u, 0);
edge[nE-1].rev = &edge[nE-2];
edge[nE-2].rev = &edge[nE-1];
}
int n;
int start, tail; //
int dis[MAXV]; // i dis[i]
int num[MAXV]; // dis i num[i];
/* <=tmp */
void buildGraph(int tmp)
{
memset(node, 0, sizeof(node));
nE = 0;
for (int i=1; i<=k; i++)
for (int j=1; j<=c; j++)
{
if (map[k+j][i] <= tmp)
addRevEdge(k+j, i, 1); // 1
}
start = k+c+1; //
tail = k+c+2; //
n = k+c+2;
for (int i=1; i<=c; i++)
addRevEdge(start, k+i, 1); // cow 1
for (int i=1; i<=k; i++)
addRevEdge(i, tail, m); // k m
}
void BFS()
{
memset(dis, -1, sizeof(dis));
memset(num, 0, sizeof(num));
int Q[MAXV], p, q;
Q[0] = tail; p = 0; q = 1;
dis[tail] = 0;
num[0] = 1;
while(p < q)
{
int u = Q[p++];
for (Edge* e = node[u]; e; e = e->next)
{
if (e->rev->cap > 0 && dis[e->v] == -1)
{
dis[e->v] = dis[u] + 1;
num[dis[e->v]]++;
Q[q++] = e->v;
}
}
}
}
int maxFlow()
{
int u, totFlow = 0;
Edge *nextEg[MAXV], *preEg[MAXV];
for (int i=1; i<=n; i++)
nextEg[i] = node[i];
u = start;
while (dis[start] < n)
{
if (u == tail) // find an augmenting path
{
int augFlow = INF;
for (int i = start; i != tail; i = nextEg[i]->v)
if (augFlow > nextEg[i]->cap)
augFlow = nextEg[i]->cap;
for (int i = start; i != tail; i = nextEg[i]->v)
{
nextEg[i]->cap -= augFlow;
nextEg[i]->rev->cap += augFlow;
nextEg[i]->flow += augFlow;
nextEg[i]->rev->flow -= augFlow;
}
totFlow += augFlow;
u = start;
}
Edge *e;
for (e = nextEg[u]; e; e = e->next)
if (e->cap > 0 && dis[u] == dis[e->v]+1)
break;
if (e) // find an admissible arc, then Advance
{
nextEg[u] = e;
preEg[e->v] = e->rev;
u = e->v;
}
else // no admissible arc, then relabel this vertex
{
if (0 == (--num[dis[u]])) break; // GAP cut, Important!
nextEg[u] = node[u];
int mindis = n;
for (e = node[u]; e; e = e->next)
if (e->cap > 0 && mindis > dis[e->v])
mindis = dis[e->v];
dis[u] = mindis + 1;
++num[dis[u]];
if (u != start)
u = preEg[u]->v;
}
}
return totFlow;
}
/* ， （I-SAP） */
void solve()
{
int low = 1, high = 200*(k+c), mid;
while (low < high)
{
mid = (low + high)/2;
buildGraph(mid);
BFS();
maxFlow() == c ? high = mid : low = mid+1;
}
printf("%d
", low);
}
void floyd()
{
int i, j, h, t = k+c;
for (h=1; h<=t; h++)
for (i=1; i<=t; i++)
for (j=1; j<=t; j++)
if (map[i][j] > map[i][h]+map[h][j])
map[i][j] = map[i][h]+map[h][j];
}
int main()
{
scanf("%d %d %d", &k, &c, &m);
for (int i=1; i<=k+c; i++)
for (int j=1; j<=k+c; j++)
{
scanf("%d", &map[i][j]);
if (map[i][j] == 0)
map[i][j] = INF;
}
floyd();
solve();
}