RT。
不知道为什么就是 Wrong on Test #1,不知道有什么错,恳请大佬帮忙找错
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define eps 1e-8
const int inf=0x3f3f3f3f;
const int Maxn=1010;
const int Maxm=1e6+10;
bool vis[Maxn];
int Maxh[Maxn],Maxl[Maxn];
int mp[Maxn][Maxn];
struct Edge{
int to;
int nxt;
}E[Maxm<<1];
int head[Maxn],tot;
void addedge(int u,int v)
{
tot++;
E[tot].to=v;
E[tot].nxt=head[u];
head[u]=tot;
}
int rmatch[Maxn];
bool dfs(int u)
{
for(int i=head[u];i;i=E[i].nxt)
{
int v=E[i].to;
if(vis[v]) continue;
vis[v]=1;
if(rmatch[v]==-1 || dfs(v))
{
rmatch[v]=u;
return true;
}
}
return false;
}
int n,m;
signed main()
{
while(~scanf("%lld%lld",&n,&m))
{
memset(rmatch,-1,sizeof(rmatch));
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&mp[i][j]);
}
}
memset(Maxh,0,sizeof(Maxh));
memset(Maxl,0,sizeof(Maxl));
memset(head,0,sizeof(head));
tot=0;
int sum=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
Maxh[i]=max(Maxh[i],mp[i][j]);
Maxl[j]=max(Maxl[j],mp[i][j]);
if(mp[i][j]>0)
{
sum+=mp[i][j]-1;
}
}
}
for(int i=1;i<=n;i++)
{
if(Maxh[i])
{
sum=sum-Maxh[i]+1;
}
}
for(int i=1;i<=m;i++)
{
if(Maxl[i])
{
sum=sum-Maxl[i]+1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(Maxh[i]==Maxl[j] && mp[i][j])
{
addedge(i,j+n);
}
}
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
{
sum+=Maxh[i]-1;
}
}
printf("%lld\n",sum);
}
return 0;
}