HDU 2236 无题II - dblank

HDU 2236 无题II

<div class="panel_title" align="left">Problem Description</div>
<div class="panel_content">这是一个简单的游戏,在一个n*n的矩阵中,找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。</div>
<div class="panel_bottom"></div>
<div class="panel_title" align="left">Input</div>
<div class="panel_content">输入一个整数T表示T组数据。
对于每组数据第一行输入一个正整数n(1<=n<=100)表示矩阵的大小。
接着输入n行,每行n个数x(0<=x<=100)。</div>
<div class="panel_bottom"></div>
<div class="panel_title" align="left">Output</div>
<div class="panel_content">对于每组数据输出一个数表示最小差值。</div>
<div class="panel_bottom"></div>
<div class="panel_title" align="left">Sample Input</div>
<div class="panel_content">
<div>1 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4</div>
</div>
<div class="panel_bottom"></div>
<div class="panel_title" align="left">Sample Output</div>
<div class="panel_content">
<div>3</div>
</div>
<div class="panel_bottom"> 思路:匈牙利匹配可以判断能否找到n个点任意两点不在同一行或者同一列。那么我们可以二分一个范围,只要在这个范围的点权可以满足所有的行和列匹配这个区间就是合法的,对于这个区间,我们可以枚举下界,然后二分上界。然后有一个优化,只有有一个行不匹配这个区间就是无效的,只有有一个区间合法,那么这个范围就是合法的。</div>

<div class="panel_bottom">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl 'n'
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100 + 10, Mod = 110119;
typedef long long  ll;
int aN, link[N], pathN, vis[N];
int n, down, up;
int dfs(int x)
{
    for(int i = 1; i<=n; i++)
    {
        if(!vis[i] && ax>=down && ax<=up)
        {
            vis[i] = 1;
            if(link[i] == -1 || dfs(link[i]))
            {
                link[i] = x;
                return 1;
            }
        }

    }
    return 0;
}
int solve()
{
    int cnt = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i<=n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(!dfs(i))
            return 0;
    }
    return 1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int minx = inf, maxx = -inf;
        scanf("%d", &n);
        for(int i = 1; i<=n; i++)
        {
            for(int j = 1; j<=n; j++)
            {
                scanf("%d", &ai);
                minx = min(ai, minx);
                maxx = max(ai, maxx);
            }
        }
        int l = 0, r = maxx - minx, mid, ok = 1, ans;
        while(l<=r)
        {
            mid = (l+r)>>1;
            ok = 0;
            for(int i = minx; i+mid<=maxx; i++)
            {
                down = i, up = i + mid;
                if(solve())
                {
                    ok = 1;
                    break;
                }
            }
            if(ok) r = mid - 1;
            else l = mid + 1;
        }
        printf("%dn", l);
    }
    return 0;
}

</div>
<div class="panel_title" align="left"></div>

相关文章

发表新评论