无题II
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1198 Accepted Submission(s): 535
Problem Description
这是一个简单的游戏，在一个n*n的矩阵中，找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。
Input
输入一个整数T表示T组数据。
对于每组数据第一行输入一个正整数n(1<=n<=100)表示矩阵的大小。
接着输入n行，每行n个数x(0<=x<=100)。
对于每组数据第一行输入一个正整数n(1<=n<=100)表示矩阵的大小。
接着输入n行，每行n个数x(0<=x<=100)。
Output
对于每组数据输出一个数表示最小差值。
Sample Input
1
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
Sample Output
3
Author
xhd
Source
直接二分差值，然后直接匈牙利算法判断是否符合即可
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#define INF 100000000
using namespace std;
int n,mp[105][105],minn,maxx,link[105],mark[105],l,r,mid,p;
bool dfs(int x)
{
for(int i=1;i<=n;i++)
{
if(mark[i]==-1&&mp[x][i]>=p&&mp[x][i]<=p+mid)
{
mark[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
bool check(int x)
{
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++)
{
memset(mark,-1,sizeof(mark));
if(!dfs(i))
return false;
}
return true;
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%d",&n);
maxx=0,minn=INF;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&mp[i][j]);
minn=min(minn,mp[i][j]);
maxx=max(maxx,mp[i][j]);
}
}
l,r,mid;
int ans=0;
l=0,r=maxx-minn;
while(l<=r)
{
mid=(l+r)>>1;
bool flag=false;
for(p=minn;p+mid<=maxx;p++)
{
if(check(mid))
{
flag=true;
break;
}
}
if(flag)
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d
",ans);
}
return 0;
}