酷暑一夏1

不忘初心，方得始终

• 于  USACO, USACO Training  阅读 

USACO Chapter3 Section3 Prob 1 Solution

一、翻译（来源）

Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。
每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。两顶点间可能有多个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一位较小的，如果还有多组解，输出第二位较小的，等等)。
输入数据保证至少有一个解。

二、题解

欧拉通路。
(1) 输出字典序最小的，边的遍历顺序：节点编号升序。因为数组链表的特性，加边时要反过来加。
(2) 根据欧拉通路特性可以分为有2个和0个奇数度的，有0个的起点编号为最小的节点编号，2个的为最小奇数度的节点的编号。（此解法未证明是正确解，但通过此解法已AC本题）
(3) 有重复边每条边都要保留（如：1->2有两条，这两条都要保留），删边时要记得删掉反向边。
(4) 逆序输出结果

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
ID: 
PROB: fence
LANG: C++
*/
#include<cstdio>
#include<algorithm>
#include<climits>
const int MAXN=500+5;
const int MAXM=2048+5;
struct Edge{int u,v,next;};
struct Input{int u,v;};
int last[MAXN][MAXN],head[MAXN],cir[MAXM],circnt,deg[MAXN];Input inp[MAXM];Edge edge[MAXM];
bool comp(Input a,Input b){return a.u==b.u?a.v>b.v:a.u<b.u;}
void AddEdge(int u,int v,int i)
{
	edge[i].u=u;edge[i].v=v;
	edge[i].next=head[u];head[u]=i;
	last[u][v]++;
}
void findcir(int x)
{
	int u,v;
	u=x;
	for(int i=head[x];i;i=edge[i].next)
	{
		v=edge[i].v;
		if(last[u][v])
		{
			last[u][v]--;last[v][u]--;
			findcir(v);
		}
	}
	cir[++circnt]=x;
}
int main()
{
	int u,v,m,min=INT_MAX,max;
	freopen("fence.in","r",stdin);
	freopen("fence.out","w",stdout);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&u,&v);
		inp[i*2-1].u=inp[i*2].v=u;
		inp[i*2-1].v=inp[i*2].u=v;
		deg[u]++;deg[v]++;
		min=std::min(min,std::min(u,v));
		max=std::max(max,std::max(u,v));
	}
	std::sort(inp+1,inp+2*m+1,comp);
	for(int i=1;i<=2*m;i++)
		AddEdge(inp[i].u,inp[i].v,i);
	for(int i=min;i<=max;i++)
		if(deg[i]%2==1)
		{
			findcir(i);
			break;
		}
	if(circnt==0) findcir(min);
	for(int i=circnt;i>=1;i--)
		printf("%d\n",cir[i]);
	return 0;
}
最近的文章

USACO Chapter3 Section3 Prob 2 Solution

一、翻译（来源）在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 2 zorkmids （z），而一个花瓶的价格是 5z 。为了吸引更多的顾客，商店举行了促销活动。促销活动把一个或多个商品组合起来降价销售，例如：三朵花的价格是 5z 而不是 6z， 两个花瓶和一朵花的价格是 10z 而不是 12z。 编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。对于上面的商品信息，购买三朵花和两个花瓶的最少花费的方案是：以优惠价购买两个花瓶和一朵花（10z），以原价购买两朵花（4z）。INPUT FORMAT：（file shopping.in)输入文件包括一些商店提供的优惠信息，接着是购物清单。（最多有5种商品）第一行 优惠方案的种类数（0 &lt;= s &lt;= 99）。第二行..第s+1 行 每一行都用几个整数来表示一种优惠方式。第一个整数 n （1 &lt;= n &lt;= 5），表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k 表示 k （1 &lt;= k &lt;= 5）个编号为 c （1 &lt;= c &lt;= 999）的商品共同构成这种优惠，最后的整数 p 表示这种优惠的优惠价（1 &lt;= p &lt;= 9999）。优惠价总是比原价低。第 s+2 行 这一行有一个整数 b （0 &lt;= b &lt;= 5），表示需要购买 b 种不同的商品。第 s+3 行..第 s+b+2 行 这 b 行中的每一行包括三个整数：c，k，p。 c 表示唯一的商品编号（1 &lt;= c &lt;= 999），k 表示需要购买的 c 商品的数量（1 &lt;= k &lt;= 5）。p 表示 c 商品的原价（1 &lt;= p &lt;= 999）。最多购买 5*5=25 个商品。OUTPUT FORMAT：(file shopping.out)只有一行，输出一个整数：购买这些物品的最低价格。 二、题解多重背包问题，对于编号问题要好好处理。 …

• 于  USACO, USACO Training 继续阅读
更早的文章

USACO 2017 January Contest, Bronze

ResultThe name was hidden.12345* = Correctx = Wrong Answer (including possibly empty or missing output file)Country Name Score notlast hps cowtipCHN ·········· 800 *********** ********** ****xxxxxx Solution …

• 于  USACO, 比赛 继续阅读