Time Limit: 20 second
Memory Limit: 20 MB
问题描述
数学家欧拉曾经解决过著名的七桥问题。下面写出七桥问题的描述：城市中有一条河，河中有 A、 D两个岛，河上有七座桥来连接两个岛及河的 B、 C两岸，问： ⑴能否刚好经过每座桥一次，既无重复也无遗漏？ ⑵能否经过桥一次后又回到原来出发点上来？ 七桥问题可以画成一个图的形式，这样七桥问题的第一问就转化成了能否一笔画成一个图的问题。 我们对无向图进行讨论,一个图能否一笔画成需要满足以下条件：先根据图的邻接矩阵求出每个顶点的度数。如果没有度数为奇数的顶点，则可以从任一点开始一笔画成一个图。如果有两个度数为奇数的顶点，则可从这两个奇数顶点中的任一点开始一笔画成一个图(这里我们按照度数大小,先选择度数较小的那个结点开始,如果度数相等则选后一个)。如果度数为奇数的顶点超过两个，则这个图不能够一笔画出。
（注：控制输出结果时，若有多种可能性，那么选择路径时，序号小的城市先输出，）
Input
第一行输入顶点个数
第二行输入图所对应的邻接矩阵
Output
输出结果,如果没有路径则输出 no solution(回车); 如果有结果,则输出路径,顶点间用->连接。
Sample Input
4 (回车) 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 (回车)
Sample Output
the road is:1->2->3->1->4->2 (回车)
【题解】
在输入矩阵的某行某列g[i][j]的时候，du[i]++,即增加i的出度。
最后for 1 ->n 扫描一遍du数组。
题目中是说如果度数相同则找靠后的，但是给的样例却是先找前面的。
所以在找的时候应该是if (du[i] % 2 == 1) -> if (du[i] < du[start]) start = du[i];
然后在扫描的时候顺便记录一下奇点的个数。
如果奇点个数>2则输出无解信息。
否则，从start开始搜索，走过一条边，就把这条边给删掉。然后继续找下一个点。
到了最后一个点的时候，判断一下还有没有边可以走到另一个点，如果有就把那个点也加入到ans数组中去。
【代码】
#include <cstdio>
#include <cstring>
#include <stdlib.h>
int n,g[100][100],du[100],jinum = 0,start = -1,num = 0,ans[100],haved = 0;
bool bo[100];
void input_data()
{
memset(du,0,sizeof(du));
memset(bo,false,sizeof(bo)); //把度数和bo数组都进行初始化操作。
scanf("%d",&n);
for (int i = 1;i <= n;i++) //输入矩阵
for (int j = 1;j <= n;j++)
{
scanf("%d",&g[i][j]);
if (g[i][j] == 1)
du[i]++; //增加出度
}
}
void dfs(int x)
{
if (!bo[x]) //如果之前都没有碰到过这个点 则找到了一个新的点，已经走过的不重复的点的个数递增；
{
bo[x] = true;
haved++;
}
ans[++num] = x; //记录下路径
if (haved == n) //如果已经走过了所有的点
{ //则输出答案。
for (int i = 1;i <= n;i++) //找一下当前这个点，还有没有点和他相连。如果有的话也加入到ans数组中
if (g[x][i] == 1)
{
ans[++num] = i;
break;
}
printf("the road is:");
for (int i = 1;i <= num-1;i++)
printf("%d->",ans[i]);
printf("%d
",ans[num]);
exit(0); //最后直接结束程序
}
for (int i = 1;i <= n;i++) //找到和x数组相连的点 删掉他们的边 进入那个点。
if (g[x][i] == 1)
{
g[x][i] = 0;g[i][x] = 0;
dfs(i);
}
}
void get_ans()
{
for (int i = 1;i <= n;i++) //统计奇点的个数 同时找到开始搜索的点。
if ( (du[i] % 2) == 1)
{
jinum++;
if ( start == -1)
start = i;
else
if (du[i] < du[start])
start = i;
}
}
void output_ans()
{
if (jinum > 2)
{
printf("no solution
");
return;
}
dfs(start);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
output_ans();
return 0;
}