2014
01-04

# The nearest fraction

Find the fraction closest to sqrt(N), the denominator of the fraction is no more than M.

The input consists of multiple test cases.For each case the input contains two integers N and M, 1<=N<=1000000, 1<=M<=1000.

The input consists of multiple test cases.For each case the input contains two integers N and M, 1<=N<=1000000, 1<=M<=1000.

9 4

3/1

HDU_2225

EK算法个人感觉就像是匈牙利算法基础上的条件增广，即只有在A[x]+B[y]==W[x,y]的时候才进行增广，同时初始化以及算法进行过程中都要保证A[x]+B[y]>=W[x,y]，如果不能实现增广再进行一定的策略降低未能匹配的xyA[x]+B[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(;;)
{

1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

3. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

4. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。