给czr老湿看的神秘代码

esp3ca1y1-

2026-10-06 17:01:47

发布于：上海

4阅读

0回复

0点赞

    #include<bits/stdc++.h>

using namespace std;

const int N = 520;
vector<int> g[N];

struct node
{
	int x, y;
};

int dp[N][N];

void solve()
{
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= n; j ++)
		{
			int x;
			cin >> x;
			
			if(x) continue;
			if(i < j)
			{
				g[i].push_back(j);
				g[j].push_back(i); 
			}
		}
	}
	
	vector<int> c(n + 1);
	vector<node> w(1);
	for(int i = 1; i <= n; i ++)
	{
		if(c[i]) continue;
		
		queue<int> q;
		q.push(i);
		int c1 = 0, c2 = 0;
		c[i] = 1;
		
		while(!q.empty())
		{
			auto u = q.front();
			q.pop();
			
			if(c[u] == 1) c1 ++;
			else c2 ++;
			
			for(auto v: g[u])
			{
				if(c[v] == c[u])
				{
					cout << "No\n";
					return;
				}
				
				if(c[v] == 0) 
				{
					c[v] = 3 - c[u];
					q.push(v);
				}
			}
		}
		w.push_back({c1, c2});
	}
	
	int ans = n + 10;
	
	dp[0][0] = 1;
	for(int i = 1; i < w.size(); i ++)
	{
		for(int j = 0; j <= n; j ++)
		{
			dp[i][j] |= dp[i - 1][j];
			if(j >= w[i].x) dp[i][j] |= dp[i - 1][j - w[i].x];
			if(j >= w[i].y) dp[i][j] |= dp[i - 1][j - w[i].y];
			if(dp[i][j] && i == (int)(w.size() - 1)) ans = min(ans, max(j, n - j));
		}
	}
	
	if(ans == n + 10)
	{
		cout << "No\n";
		return;
	}
	cout << "Yes\n";
	cout << ans << '\n';
}

signed main()
{
	solve();
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论