首页 > 代码库 > 【图论】
【图论】
1-21;
之前打过图论,只是粗略的打过......;
所以先复习一下.....
骑马修栅栏
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int f;
int sum[600];
int ans[10000];
int o=1;
struct
{
int a,b,c;
}
vvv[3000000];
int num[1045][1045]={};
int flagx;
int ss=0;
int flag[100000];
int fl[1045][1045]={};
int dfs(int w,int u)
{
cout<<w<<"-"<<endl;
for(int i=1;i<=o;i++)
{
if(fl[w][sum[i]]>0)
{
fl[w][sum[i]]--;
fl[sum[i]][w]--;
dfs(sum[i],u+1);
ans[ss--]=sum[i];
if(ss==1)for(int i=1;i<=f+1;i++)
cout<<ans[i]<<endl;
}
}
return 0;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int a,b;
int w,t;
cin>>f;
for(int i=1;i<=f;i++)
{
cin>>w>>t;
fl[w][t]++;
fl[t][w]++;
if(flag[t]==0){flag[t]=1;sum[o++]=t;}
if(flag[w]==0){flag[w]=1;sum[o++]=w;}
}
sort(sum+1,sum+o);
int aa=0;
int kk;
int flag=1;
for(int i=1;i<=o-1;i++)
{
for(int u=1;u<=o-1;u++)
{
aa+=fl[sum[i]][sum[u]];
}
if(aa%2==1)
{kk=sum[i];flag=0;break;}
}
ss=f+1;
if(flag==1)kk=1;ans[1]=kk;
dfs(kk,1);
}
其实以前打的时候超时.....因为遍历了n*n次.....后来想了想(也是以前)...根据欧拉路可以选择起点的....;但是仍然是超时的.......;
后来在老师的帮助下迷迷糊糊就过了、、、
今天又看了看,总算看出点门道‘、、、
这个题的核心是‘欧拉路遍历+输出方式;
因为答案要求是字典序输出的,所以遍历的时候从最小值遍历就行。
欧拉路:
如果连通图入度都为偶数....那么肯定为欧拉路而且就算瞎走也可以走成欧拉路....所以如果图的入度都是偶数、直接遍历输出即可。
当图的入度中有奇数时............如果两个入度为奇数,这两个点分别为欧拉路的入口和出口、、、这时候瞎走就不行了......
奇数分析
一开始肯定先瞎走
1-5 5-4 4-2 4-5 5-4;
对。。。然后我们会发现 瞎走是不行的...因为走完4-2后就进了死胡同...............
那该怎么办呢........
我们可以发现 对于入度为奇数的欧拉路来说最先进入死胡同的肯定是终点...在上图中4-2是通往死胡同的路.....所以我们可以确定的是最后一个点 是 ’2‘而倒数第二个点是’4‘;
而剩余的路就成了这个样子
首先对于剩余的路来说,起点是4--而终点也是4, 我们效仿之前的做法...那么倒数第三个点肯定是4,倒数第四个点是5,第5个点还是4.以此推之..............
最后得出的结论是...一条道走到黑..如果到头,说明它靠后,就让它进队,最后反着输出....
代码实现就是回溯的时候进队(回溯说明撞墙了嘛)。
【图论】