1123 铲雪车
解题报告：这题其实不知道欧拉路径也能做出来，由于铲雪车在路径上，那么只要算出来所有路径长*2，因为两边都要铲，除以速度就是答案了。
#include<iostream>
#include<cmath>
using namespace std;
double get_dis(int x1,int y1,int x2,int y2)
{
return sqrt(1.0*(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
int x,y;
cin>>x>>y;
double sum=0;
int x1,y1,x2,y2;
while(cin>>x1>>y1>>x2>>y2)
{
sum+=get_dis(x1,y1,x2,y2);
}
sum/=10000;
int h=(int)sum;
sum-=h;
int m=sum*60+0.5;
printf("%d:%02d\n",h,m);
return 0;
}
1184.欧拉回路
解题报告：其实就是爆搜，从一个不是孤立的点开始爆搜，这里爆搜要有优化，&i就是为了改变h[u]，这样删完边能从m^2的复杂度优化成m。最后在回溯的时候记录边的编号，再逆序输出才是真正的欧拉路径。
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=400010;
int h[N],w[M],ne[M],idx,e[M];
int din[N],dout[N];
int cnt;
int ans[M/2];
int type;
int n,m;
bool st[M];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
for(int &i=h[u];~i;)
{
if(st[i])
{
i=ne[i];
continue;
}
st[i]=true;
if(type==1)
st[i^1]=true;
int t;
if(type==1)
{
t=i/2+1;
if(i&1) t=-t;
}
else
t=i+1;
int j=e[i];
i=ne[i];
dfs(j);
ans[++cnt]=t;
}
}
int main()
{
scanf("%d",&type);
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
dout[a]++,din[b]++;
if(type==1)
add(b,a);
}
if(type==1)
{
for(int i=1;i<=n;i++)
if(din[i]+dout[i]&1)
{
puts("NO");
return 0;
}
}
else
{
for(int i=1;i<=n;i++)
if(din[i]!=dout[i])
{
puts("NO");
return 0;
}
}
for(int i=1;i<=n;i++)
{
if(h[i]!=-1)
{
dfs(i);
break;
}
}
if(cnt<m)
{
puts("NO");
return 0;
}
puts("YES");
for(int i=cnt;i;i--)
printf("%d ",ans[i]);
puts("");
return 0;
}
AcWing 1124. 骑马修栅栏
解题报告：这题就是欧拉路径的无向图，由于没有special judge，我们就要想想如何输出字典序最小的欧拉路径，其实可以每次搜编号最小的点，然后逆序输出必定是字典序最小的。
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=1124;
int g[N][N];
int ans[M];
int cnt;
int d[N];
int m;
int n=500;
void dfs(int u)
{
for(int i=1;i<=n;i++)
if(g[u][i])
{
g[u][i]--;
g[i][u]--;
dfs(i);
}
ans[++cnt]=u;
}
int main()
{
cin>>m;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a][b]++;
g[b][a]++;
d[a]++;
d[b]++;
}
int start=1;
while(!d[start]) start++;
for(int i=1;i<=n;i++)
if(d[i]%2)
{
start=i;
break;
}
dfs(start);
for(int i=cnt;i;i--)
printf("%d\n",ans[i]);
return 0;
}
这题只要判断是否存在有向图的欧拉路径就行了，如果只存在1个终点（入度比出度大一）和初点（入度比出度少一）或者0个（环的情况）就能存在了，并且图还要是联通的，判断图的连通性可以用并查集。
#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
bool st[N];
int din[N],dout[N];
char str[1100];
int p[N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(din,0,sizeof din);
memset(dout,0,sizeof dout);
memset(st,0,sizeof st);
int n;
scanf("%d",&n);
for(int i=0;i<26;i++)
p[i]=i;
for(int i=0;i<n;i++)
{
scanf("%s",str);
int len=strlen(str);
int a=str[0]-'a',b=str[len-1]-'a';
st[a]=true,st[b]=true;
din[b]++,dout[a]++;
p[find(a)]=find(b);
}
int end=0,start=0;
bool flag=true;
for(int i=0;i<26;i++)
{
if(st[i])
{
if(din[i]==dout[i]) continue;
if(din[i]==dout[i]+1) end++;
else if(din[i]+1==dout[i]) start++;
else flag=false;
}
}
if(flag&&!(end==1&&start==1)&&!(end==0&&start==0)) flag=false;
int t=-1;
for(int i=0;i<26;i++)
{
if(st[i])
{
if(t==-1||find(i)==t) t=find(i);
else
{
flag=false;
break;
}
}
}
if(!flag)
puts("The door cannot be opened.");
else
puts("Ordering is possible.");
}
return 0;
}
京公网安备 11010502036488号