首页 > ACM题库 > HDU-杭电 > hdu 2225 The nearest fraction-二分图-[解题报告]C++
2014
01-04

hdu 2225 The nearest fraction-二分图-[解题报告]C++

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]的值,这样在进行增广的过程中就可以保证每次最先达成的匹配都是最优的。

在寻找增广路的过程中,如果发现不能进行增广,那么我们会得到一棵交错树,其中可以把x顶点全部看做叶子节点。这时我们用一个变量slack表示需要进行修改的幅度,其值等于min{A[x]+B[y]-W[x,y]}(其中x为交错树中的xy为不在交错树中的且与交错树中的某个x相连的y),并且使交错树中的x对应的A[x]都减去一个slack,交错树中的y都加上一个slack。进行这样的操作后,我们发现如果xy都在交错树中,那么A[x]+B[y]的值没有变,因而不会影响到已经匹配的xy,如果x在交错树中而y不在交错树中,这样A[x]+B[y]的值会减小,并且一定存在某一对或几对A[x]+B[y]的值为0,这样就为下一次循环时找到增广路提供了可能。

#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(;;)
        {


解题转自:http://www.cnblogs.com/staginner/archive/2011/10/04/2198942.html


  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树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  5. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。