C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Ural 1080 Map Coloring 解题报告

Posted on 2011-11-03 13:57 C小加 阅读(1664) 评论(0)  编辑 收藏 引用 所属分类: 解题报告
BFS,我写的代码有点冗杂,题很水,不想优化了。。写完后感觉并查集可以过。
#include <cstring>
#include 
<queue>
using namespace std;
const int MAXN=103;
int n;
int map[MAXN][MAXN];
int col[MAXN];
queue
<int> que;


void Init()
{
    memset(map,
0,sizeof(map));
    memset(col,
-1,sizeof(col));
}
void Read()
{
    
int t;
    cin
>>n;
    
for(int i=1;i<=n;i++)
    {
        cin
>>t;
        
while(t)
        {
            map[i][t]
=map[t][i]=1;
            cin
>>t;
        }
    }
}
bool BFS(int k)
{
    que.push(k);
    
if(col[k]==-1)
    col[k]
=0;
    
while (!que.empty())
    {

        
int f=que.front();
        que.pop();
        
int e=col[f];
        
for (int i=1;i<=n;i++)
        {
             
if(map[f][i])
            {
                
if(col[i]==-1)
                {
                    que.push(i);
                    col[i]
=(e+1)%2;
                }
                
else if(col[i]==e) return false;

            }
        }

    }
    
return true;
}

int main()
{
    Init();
    Read();
    
int flag=1;
    
for(int i=1;i<=n;i++)
    {
        
if(!BFS(i))
        {
            flag
=0;
            
break;
        }
    }
    
if(flag)
    {
        
for (int i=1;i<=n;i++)
        {
            cout
<<col[i];
        }
        cout
<<endl;
    }
    
else
    {
        cout
<<-1<<endl;
    }

    
return 0;
}杂。。题比较水,不想优化了。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理