bzoj 3979: [WF2012]infiltration【瞎搞+随机化】

参考：https://www.cnblogs.com/ccz181078/p/5622200.html

非常服气.jpg

就是random_shuffle几次然后顺着找，ans取min...

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

using namespace std;

int n,ans,cas,a[100],tot,c[100],s[100],top;

char ch[100][100];

int main()

{

	srand(1844677);

	while(~scanf("%d",&n))

	{

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

		{

			scanf("%s",ch[i]),ch[i][i]='1';

			for(int j=0;j<n;j++)

				ch[i][j]-='0';

		}

		ans=n;

		int ca=180;

		while(ca--&&ans>1)

		{

			top=0;

			for(tot=0;tot<n;tot++)

				a[tot]=tot,c[tot]=0;

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

				for(int j=0;j<n;j++)

					if(ch[i][j])

						++c[j];

			for(int t=0;t<5;t++)

			{

				random_shuffle(a,a+tot);

				for(int i=0;i<tot;i++)

				{

					int x=a[i];

					bool ed=1;

					for(int j=0;j<n;j++)

						if(ch[x][j]>=c[j])

						{

							ed=0;

							break;

						}

					if(ed)

					{

						for(int j=0;j<n;j++)

							if(ch[x][j])

								c[j]--;

						s[top++]=x;

						a[i--]=a[--tot];

					}

				}

				if(tot<ans)

					ans=tot;

				if(!top)

					continue;

				int w=rand()%top,x=a[tot++]=s[w];

				s[w]=s[top--];

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

					if(ch[x][i])

						c[i]++;

			}

		}

		printf("Case %d: %d\n",++cas,ans);

	}

	return 0;

}

/*

2

00

10

3

010

001

100

5

01000

00011

11001

10100

10010

4

0100

0000

1100

1110

4

0011

1011

0001

0000

4

0101

0010

1001

0100

6

001110

100001

010010

011010

010001

101100

4

0000

1001

1100

1010

7

0100011

0000100

1100001

1110111

1010011

0110000

0100010

7

0010001

1011111

0001111

1000110

1000000

1000100

0001110

*/