【JZOJ1319】邮递员

　

邮递员

description

邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那遥远乡村的所有村子和小路至少一次的邮路（输入数据将会保证这么一条路是一定存在的）。

但是，每条路线都是有一个花费的。各个村子里的村民希望邮递员到达他们村子的时间越早越好。因此，各个村子里的人们采用了一些措施：假设第i号村子是邮递员在他的邮递路线上到达的第k个不同的村子。如果k<=w( i )，那么这个村子的村民就会付给邮局w( i )-k欧元。当然，如果k>w(i)，邮局也同意付k- w( i )欧元给这个村子，重复经过村子不重复收费。此外，邮递员每经过一条小路，邮局也要付给邮递员1欧元作为补贴。

现在有n个村子，编号依次为1到n。邮局就位于1号村子，因此邮递员的传递路线从这里开始，也从这个村子结束。能够离开每个村子的路口的数目一定是2，4或者8。这里允许出现同样的村子间存在多条小路，或者某条小路构成了一个自环的情况。

你的任务是设计一个路线使得邮局赚的钱最多(或者说赔的钱最少。如果有多种最优解，输出字典序最小的。

---

analysis

• 看懂题了的话，其实对于任意一种走法，费用都不会变，赚的钱就是${\sum }_{i=1}^{n}w\left[i\right]-{\sum }_{i=1}^{n}i$∑i=1n​w[i]−∑i=1n​i

• 那么其实题目就是要我们找一条字典序最小的欧拉回路

• $n$n很小且保证合法，那就从$1$1开始，从能走的最小点开始走就行了

• 最后把记录下来的点逆序输出即可

---

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 205
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define O3 __attribute__((optimize("-O3")))

using namespace std;

ll f[MAXN][MAXN];
ll ans[MAXN*10];
ll n,m,tot;

O3 inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
O3 inline void dfs(ll x)
{
	fo(i,1,n)if (f[x][i])f[x][i]--,f[i][x]--,dfs(i);
	ans[++tot]=x;
}
O3 int main()
{
	//freopen("T2.in","r",stdin);
	n=read(),m=read();
	fo(i,1,n)read();
	fo(i,1,m){ll x=read(),y=read();f[x][y]++,f[y][x]++;}
	dfs(1);
	printf("%lld\n",tot-1);
	fd(i,tot,1)printf("%d ",ans[i]);
	return 0;
}

相关阅读