Problem Description
度度熊有一个可能是整数规划的问题：
给定 n×n 个整数 ai,j(1≤i,j≤n)，要找出 2n 个整数 x1,x2,…,xn,y1,y2,…,yn 在满足 xi+yj≤ai,j(1≤i,j≤n) 的约束下最大化目标函数 ∑ni=1xi+∑ni=1yi，
你需要帮他解决这个整数规划问题，并给出目标函数的最大值。
Input
第一行包含一个整数 T，表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据：
第一行包含一个整数 n，表示该整数规划问题的规模。
接下来 n 行，每行包含 n 个整数，其中第 i 行第 j 列的元素是 ai,j。
保证 1≤T≤20，1≤n≤200，−109≤ai,j≤109(1≤i,j≤n)。
Output
对于每组测试数据，输出一行信息 "Case #x: y"（不含引号），其中 x 表示这是第 x 组测试数据，y 表示目标函数的最大值，行末不要有多余空格。
Sample Input
2
1
0
2
1 2
3 4
Sample Output
Case #1: 0
Case #2: 5
#include
using namespace std;
typedef long long ll;
const int N=207,NPOS=-1;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct KuhnMunkres
{
int n;//左右集合点数
ll a[N][N];
ll hl[N],hr[N],slk[N];//hl hr 左边集合的期望值，右边集合的期望值
int fl[N],fr[N],vl[N],vr[N],pre[N],q[N],ql,qr;//fl fr,左右匹配对应的点 vl,vr用于bfs标记,
int check(int i)
{
if(vl[i]=1,fl[i]!=NPOS)return vr[q[qr++]=fl[i]]=1;
while(i!=NPOS)swap(i,fr[fl[i]=pre[i]]);
return 0;
}
void bfs(int s)
{
fill(slk,slk+n,INF);
fill(vl,vl+n,0);
fill(vr,vr+n,0);
q[ql=0]=s;
vr[s]=qr=1;
for(ll d;;)
{
for(; ql for(int i=0,j=q[ql]; i if(d=hl[i]+hr[j]-a[i][j],!vl[i]&&slk[i]>=d)
if(pre[i]=j,d)slk[i]=d;
else if(!check(i))return;
d=INF;
for(int i=0; i if(!vl[i]&&d>slk[i])d=slk[i];
for(int i=0; i<n; ++i)
{
if(vl[i])hl[i]+=d;
else slk[i]-=d;
if(vr[i])hr[i]-=d;
}
for(int i=0; i<n; ++i)
if(!vl[i]&&!slk[i]&&!check(i))return;
}
}
void ask()
{
fill(pre,pre+n,NPOS);
fill(fl,fl+n,NPOS);
fill(fr,fr+n,NPOS);
fill(hr,hr+n,0);
for(int i=0; i<n; ++i) hl[i]=*max_element(a[i],a[i]+n);
for(int j=0; j<n; ++j) bfs(j);
}
} km;
int main()
{
int n;
int QAQ,kase=0;
scanf("%d",&QAQ);
while(QAQ--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%lld",&km.a[i][j]);
km.a[i][j]=-km.a[i][j];
}
}
km.n=n;
km.ask();
long long ans=0;
for(int i=0; i<n; ++i)
ans+=km.a[i][km.fl[i]];
printf("Case #%d: %lld\n",++kase,-ans);
}
}
————————————————
版权声明：本文为CSDN博主「zstu_zy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zstu_zy/article/details/82895378