一笔画成

2014年5月2日3,0700

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1442

题目描述

一个图能否一笔画成，如果能请你每次都从当前最小编号的点开始画起，如果不行，则输出“no answer”

输入

4
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

输出

1 2 3 4 2

题解

诶，这题是无向图。。

首先用并查集判断图是否连通，这个略过。。

然后图中要有0或2个度为奇数的点

如果是0个，则任意一个点都可以为起点，且为终点。

2个的话当然一个起点一个终点，dfs输出路径，同时保证每条边只走一次，大概这样

#include<iostream>
#include<cstdio>
using namespace std;
int n,tot,d[1001],fa[1001],bg,ed;
bool mp[1001][1001],vis[1001][1001];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void dfs(int x)
{
	printf("%d ",x);
	for(int i=1;i<=n;i++)
	   if(mp[x][i]&&!vis[x][i])
	       {vis[x][i]=vis[i][x]=1;dfs(i);}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	    {
	    	scanf("%d",&mp[i][j]);
	    	if(mp[i][j]==1)
			{
			    d[i]++;
	        	int p=find(i),q=find(j);
	        	if(p!=q){fa[p]=fa[q];tot++;}
	        } 
	    }
	if(tot!=n-1){printf("no answer");return 0;}
	for(int i=1;i<=n;i++)
	   if(d[i]&1)
	   {
	       if(!bg)bg=i;
	       else if(!ed)ed=i;
	       else {printf("no answer");return 0;}
	   }
	if(bg)dfs(bg);
    else dfs(1);
	return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

int n,tot,d[1001],fa[1001],bg,ed;

bool mp[1001][1001],vis[1001][1001];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void dfs(int x)

{

printf("%d ",x);

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

if(mp[x][i]&&!vis[x][i])

{vis[x][i]=vis[i][x]=1;dfs(i);}

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)fa[i]=i;

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

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

{

scanf("%d",&mp[i][j]);

if(mp[i][j]==1)

{

d[i]++;

int p=find(i),q=find(j);

if(p!=q){fa[p]=fa[q];tot++;}

}

if(tot!=n-1){printf("no answer");return 0;}

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

if(d[i]&1)

{

if(!bg)bg=i;

else if(!ed)ed=i;

else {printf("no answer");return 0;}

}

if(bg)dfs(bg);

else dfs(1);

return 0;

}

「BZOJ3033」太鼓达人 »

hzwer.com _ Home | http://hzwer.com

一笔画成

题目描述

输入

输出

题解

分类目录

热门文章

Myfriends

近期评论