求助
查看原帖
求助
368204
ShanQing楼主2022/12/26 21:18

自己调试后发现可能是板子出问题了,其他地方貌似没有问题,有没有dalao帮忙看看这板子有没有锅

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[40][40],ans;
int gauss()
{
	int c,r;
	for(c=1,r=1;c<=n;++c)
	{
		int t=r;
		for(int i=r;i<=n;++i)
		{
			if(a[i][c])
			{
				t=i;
				break;
			}
		}
		if(!a[t][c]) continue;
		for(int i=c;i<=n+1;++i)
		{
			swap(a[t][i],a[r][i]);
		}
		for(int i=r+1;i<=n;++i)
		{
			if(a[i][c])
			{
				for(int j=c;j<=n+1;++j)
				{
					a[i][j]^=a[r][j];
				}
			}
		}
		++r;
	}
	if(r<n) return 0;
	for(int i=n;i>=1;--i)
	{
		for(int j=i+1;j<=n;++j)
		{
			a[i][n+1]^=a[i][j]&a[j][n+1];
		}
	}
	return 1;
}
int p[40];
void dfs(int dp,int cnt)
{
	if(cnt>=ans) return;
	if(!dp)
	{
		ans=cnt;
		return;
	}
	if(!a[dp][dp])
	{
		dfs(dp-1,cnt);
		p[dp]=1;
		dfs(dp-1,cnt+1);
		p[dp]=0;
	}
	else
	{
		int now=a[dp][n+1];
		for(int i=dp+1;i<=n;++i)
		{
			if(a[dp][i]&p[i]) now^=p[i];
		}
		dfs(dp-1,cnt+now);
	}
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i) a[i][i]=a[i][n+1]=1;
	while(m--)
	{
		int s,t;
		scanf("%lld%lld",&s,&t);
		a[s][t]=a[t][s]=1;
	}
	int res=gauss();
	if(res)
	{
		ans=0;
		for(int i=1;i<=n;++i) ans+=a[i][n+1];
		printf("%lld\n",ans);
	}
	else
	{
		ans=2e9;
		dfs(n,0);
		printf("%lld\n",ans);
	}
	return 0;
}
2022/12/26 21:18
加载中...