在本地是可以跑对至少一部分数据的,(测试点1就是样例,可以跑对),但是提交之后莫名其妙显示我的第一行第一列是“-”,而不是5,没搞明白
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
typedef long long int LL;
const int N = 105,INF = 0x7fffffff;
int mp[N][N],lx[N],ly[N],visx[N],visy[N],link[N];
int n,tmp,v;
bool dfs(int x)
{
visx[x] = 1;
for(int i=1; i<=n; i++){
if(!visy[i] && lx[x]+ly[i]==mp[x][i]){
visy[i] = 1;
if(!link[i] || dfs(link[i])){
link[i] = x;
return true;
}
}
}
return false;
}
int one()
{
int ans;
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
lx[i] = std::max(lx[i],mp[i][j]);
}
for(int i=1; i<=n; i++){
while(true){
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
tmp = INF;
if(dfs(i)) break;
for(int i=1; i<=n; i++){
if(visx[i]){
for(int j=1; j<=n; j++){
if(!visy[j]){
tmp = std::min(tmp,lx[i]+ly[j]-mp[i][j]);
}
}
}
}
for(int j=1; j<=n; j++){
if(visx[j]) lx[j] -= tmp;
if(visy[j]) ly[j] += tmp;
}
}
}
for(int i=1; i<=n; i++){
ans += ly[i] + lx[link[i]];
}
return ans;
}
int main()
{
//freopen("D:\\EdgeDownloadPlace\\P4014_1.in","r",stdin);
scanf("%d",&n);
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
scanf("%d",&v);
mp[i][j] = -v;
}
for(int i=0; i<N; i++) lx[i] = -INF;
printf("%d\n",-one());
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
mp[i][j] = -mp[i][j];
}
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(link,0,sizeof(link));
printf("%d\n",one());
return 0;
}