#6472. 「ICPC World Finals 2017」难以置信的任务 Mission Improbable

可以简化一下问题，假设Patrick把箱子都拿走但是原来有箱子的位置留下一个，现在要放箱子使得每行每列最大值都满足，最少放多少个。

设第\(i\)行的最大值是\(H(i)\)，第\(i\)列的是\(W(i)\)。没有箱子的行可以不用去管，假设每行每列都有一个地方放\(H(i)/W(i)\)，现在如果有一个\(H(i)=W(j)\)，而且原来\((i,j)\)位置上有箱子，那么就可以在\((i,j)\)位置上放\(H(i)\)个箱子同时满足第\(i\)行与第\(j\)列，获得\(H(i)-1\)的收益。

这题就做完了，统一答案随便乱搞。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

ll A[101][101],H[101],W[101];

int S,T,fir[210],dis[30010],nxt[30010],w[30010],id=1;

ll cost[30010];

il vd link(int a,int b,ll d){

	nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=1,cost[id]=d;

	nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0,cost[id]=-d;

}

il bool Mincost(ll&total){

	static ll dist[210];

	static int que[210],hd,tl,lst[210];

	static bool inq[210];

	memset(dist,63,sizeof dist);

	dist[S]=0;hd=tl=0;que[tl++]=S;inq[S]=1;

	lst[T]=0;

	while(hd^tl){

		int x=que[hd];

		for(int i=fir[x];i;i=nxt[i])

			if(w[i]&&dist[dis[i]]>dist[x]+cost[i]){

				dist[dis[i]]=dist[x]+cost[i],lst[dis[i]]=i;

				if(!inq[dis[i]])inq[dis[i]]=1,que[tl++]=dis[i],tl%=210;

			}

		inq[x]=0,++hd,hd%=210;

	}

	for(int i=lst[T];i;i=lst[dis[i^1]])w[i]=0,w[i^1]=1,total-=cost[i];

	return lst[T];

}

int main(){

	int n=gi(),m=gi();

	ll ans=0;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j){

			A[i][j]=gi();

			if(A[i][j])ans+=A[i][j]-1;

			H[i]=std::max(H[i],A[i][j]);

			W[j]=std::max(W[j],A[i][j]);

		}

	for(int i=1;i<=n;++i)if(H[i])ans-=H[i]-1;

	for(int i=1;i<=m;++i)if(W[i])ans-=W[i]-1;

	S=0,T=n+m+1;

	for(int i=1;i<=n;++i)link(S,i,0);

	for(int i=1;i<=m;++i)link(i+n,T,0);

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			if(A[i][j]&&H[i]==W[j]&&H[i])link(i,n+j,-H[i]+1);

	while(Mincost(ans));

	printf("%lld\n",ans);

	return 0;

}