uva 193

本文主要是介绍uva 193，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一张图染色。只有黑白两种，相连的点是不能都是黑色的（白色的可以），问你染黑色的最大数，并输出染黑色的点

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 110;int m,n,k;
int graph[MAXN][MAXN];
int color[MAXN];
bool vis[MAXN][MAXN];
int blackNodes;
int maxblackNodes;
int ans[MAXN];void dfs(int cur,int blacks)
{int i,j;if (cur > n){if (blacks > maxblackNodes){maxblackNodes = blacks;for ( i = 0 ; i <= n ; i++)ans[i] = color[i];}return ;}bool flag = true ;for (i =1 ; i <= n; i++)    //判断这个点如果要染黑是否会冲突{if (graph[cur][i] && color[i] == 1){flag = false;break;}}if (blacks + n - cur + 1 <= maxblackNodes)  //减枝return ;if (flag){color[cur] = 1 ;dfs(cur+1,blacks+1);color[cur] = 0 ;}dfs(cur+1,blacks);
}int main()
{int i,j;cin>>m;while (m--){memset(graph,0,sizeof(graph));memset(color,0,sizeof(color));memset(ans,0,sizeof(ans));maxblackNodes = 0;cin>>n>>k;for(i = 0; i < k; i++){int iEdge,oEdge;cin>>iEdge>>oEdge;graph[iEdge][oEdge] = graph[oEdge][iEdge] = 1 ;}dfs(1,0);cout<<maxblackNodes<<endl;bool first = true;for (int i = 1; i <= n; i++){if (ans[i] == 1) {if(first)first = false;else cout<<" ";cout<<i;}}cout<<endl;}return 0 ;
}

这篇关于uva 193的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---