HDU 2225小康に走って大金を稼ぐ
5441 ワード
HDU_2225
これは私の最初の二分図の最適マッチングのテーマです.
EKアルゴリズムの個人的な感覚はハンガリーアルゴリズムに基づいた条件の広がり,すなわちA[x]+B[y]==W[x,y]の場合にのみ広がりを行うとともに,初期化およびアルゴリズムの進行中にA[x]+B[y]>=W[x,y]を保証し,広がりを実現できなければマッチングできなかったx,yのA[x]+B[y]の値を一定の戦略で低減し,これにより、拡張を行う過程で、最初に達成されるマッチングが毎回最適であることが保証される.
拡張路を探す過程で,拡張ができないことに気づいたら,x頂点をすべて葉ノードと見なすことができる交錯木を得る.このとき、変数slackを用いて修正が必要な振幅を表し、その値はmin{A[x]+B[y]-W[x,y]}(xはインタリーブツリーのxであり、yはインタリーブツリーの中になく、インタリーブツリーの中のあるxに接続されたyである)に等しく、インタリーブツリーのxに対応するA[x]に1つのslackを減算し、インタリーブツリーのyに1つのslackを加算する.このような操作を行うと,x,yがともにインタリーブツリーにある場合,A[x]+B[y]の値は変化しないため,一致したx,yには影響しないことが分かった.これにより、次のサイクル時に拡張路を見つけることが可能になります.
これは私の最初の二分図の最適マッチングのテーマです.
EKアルゴリズムの個人的な感覚はハンガリーアルゴリズムに基づいた条件の広がり,すなわちA[x]+B[y]==W[x,y]の場合にのみ広がりを行うとともに,初期化およびアルゴリズムの進行中にA[x]+B[y]>=W[x,y]を保証し,広がりを実現できなければマッチングできなかったx,yのA[x]+B[y]の値を一定の戦略で低減し,これにより、拡張を行う過程で、最初に達成されるマッチングが毎回最適であることが保証される.
拡張路を探す過程で,拡張ができないことに気づいたら,x頂点をすべて葉ノードと見なすことができる交錯木を得る.このとき、変数slackを用いて修正が必要な振幅を表し、その値はmin{A[x]+B[y]-W[x,y]}(xはインタリーブツリーのxであり、yはインタリーブツリーの中になく、インタリーブツリーの中のあるxに接続されたyである)に等しく、インタリーブツリーのxに対応するA[x]に1つのslackを減算し、インタリーブツリーのyに1つのslackを加算する.このような操作を行うと,x,yがともにインタリーブツリーにある場合,A[x]+B[y]の値は変化しないため,一致したx,yには影響しないことが分かった.これにより、次のサイクル時に拡張路を見つけることが可能になります.
#include<stdio.h>
#include<string.h>
#define MAXD 310
#define INF 1000000000
int n, yM[MAXD], visx[MAXD], visy[MAXD];
int G[MAXD][MAXD], A[MAXD], B[MAXD], slack;
void init()
{
int i, j;
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
scanf("%d", &G[i][j]);
for(i = 0; i < n; i ++)
{
A[i] =0;
for(j = 0; j < n; j ++)
if(G[i][j] > A[i])
A[i] = G[i][j];
}
memset(B, 0, sizeof(B));
}
int searchpath(int u)
{
int v, temp;
visx[u] = 1;
for(v = 0; v < n; v ++)
if(!visy[v])
{
temp = A[u] + B[v] - G[u][v];
if(temp == 0)
{
visy[v] = 1;
if(yM[v] == -1 || searchpath(yM[v]))
{
yM[v] = u;
return 1;
}
}
else if(temp < slack)
slack = temp;
}
return 0;
}
void KM()
{
int i, j;
memset(yM, -1, sizeof(yM));
for(i = 0; i < n; i ++)
for(;;)
{
slack = INF;
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if(searchpath(i))
break;
for(j = 0; j < n; j ++)
{
if(visx[j])
A[j] -= slack;
if(visy[j])
B[j] += slack;
}
}
}
void printresult()
{
int i, ans = 0;
for(i = 0; i < n; i ++)
ans += G[yM[i]][i];
printf("%d
", ans);
}
int main()
{
int i;
while(scanf("%d", &n) != EOF)
{
init();
KM();
printresult();
}
return 0;
}