自动搬运

查看原文

来自洛谷，原作者为

	ButterflyDew life is hard

搬运于2025-08-24 21:55:07，当前版本为作者最后更新于2019-02-24 18:45:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这不是个贪心吗？

怎么都最小链覆盖=最大点独立集去了

注意到一个点出度最多只有2，可以贪心一下出度的去向

按读入顺序处理就可以，维护一个$res_i$数组，表示上一行第$i$列可以流给下面那个格子的次数，然后如果当前这个格子不够用，从右往左把所有的还有次数的$res$拿过来给当前格子用就可以了。

考虑这样的正确性，每个格子已经用了上面的，当然继续从左边的用啦

Code:

#include <cstdio>
#include <cctype>
#include <cstring>
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=1010;
const int inf=0x3f3f3f3f;
int res[N],s[N],tot;
void work()
{
	memset(res,0,sizeof res);
	int n,m,ans=0;
	read(n),read(m);
	for(int a,i=1;i<=n;i++)
	{
	    res[s[tot=1]=0]=inf;
	    for(int j=1;j<=m;j++)
		{
			read(a);
			if(a>res[j])
			{
			    int d=a-res[j];
				while(res[s[tot]]<d) d-=res[s[tot]],res[s[tot--]]=0;
				res[s[tot]]-=d;
				res[j]=a;
			}
			s[++tot]=j;
		}
		ans+=inf-res[0];
	}
	printf("%d\n",ans);
}
int main()
{
	int T;read(T);
	while(T--) work();
	return 0;
}