「TJOI2015」组合数学

这不是个贪心吗？

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

注意到一个点出度最多只有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;

}

---

2019.2.24