现在的位置: 首页 > 综合 > 正文

HDU 3488 Tour

2012年10月04日 ⁄ 综合 ⁄ 共 1182字 ⁄ 字号 评论关闭

HDU_3488

值得一提的是,如果我们用KM算法求最小权完美匹配时,要把边的权值初始化成MAX-G[i][j]然后去求最大权的完美匹配,计算结果的时候再转化回来即可。

如果把G[i][j]初始化成-G[i][j]去求最大权的完美匹配的话,我写的程序会超时,暂时没有明白是这个想法有问题还是我的写法有问题。

#include<stdio.h>
#include<string.h>
#define MAXD 210
#define INF 1000000000
#define MAX 10001
int yM[MAXD], G[MAXD][MAXD], N;
int visx[MAXD], visy[MAXD], slack, A[MAXD], B[MAXD];
void init()
{
int i, j, M, temp, u, v;
memset(G, 0, sizeof(G));
scanf("%d%d", &N, &M);
for(i = 0; i < M; i ++)
{
scanf("%d%d%d", &u, &v, &temp);
u --;
v --;
if(!G[u][v] || MAX -temp > G[u][v])
G[u][v] = MAX - temp;
}
}
int searchpath(int u)
{
int v, temp;
visx[u] = 1;
for(v = 0; v < N; v++)
if(G[u][v] && !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 EK()
{
int i, j;
for(i = 0; i < N; i ++)
{
A[i] = 0;
for(j = 0; j < N; j ++)
if(G[i][j] && G[i][j] > A[i])
A[i] = G[i][j];
}
memset(B, 0, sizeof(B));
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, res = 0;
for(i = 0; i < N; i ++)
res += (MAX - G[yM[i]][i]);
printf("%d\n", res);
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
init();
EK();
printresult();
}
return 0;
}


抱歉!评论已关闭.