[usaco]4.1.3 Fence Rails 多维背包问题,dfsid

 Fence Rails
Burch, Kolstad, and Schrijvers
Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but he’s having a problem with the rails. The local lumber store has dropped off boards of varying lengths; Farmer
John must create as many of the rails he needs from the supplied boards.

Of course, Farmer John can cut the boards, so a 9 foot board can be cut into a 5 foot rail and a 4 foot rail (or three 3 foot rails, etc.). Farmer John has an `ideal saw’, so ignore the `kerf’ (distance lost during sawing); presume that perfect cuts can
be made.

The lengths required for the rails might or might not include duplicates (e.g., a three foot rail and also another three foot rail might both be required). There is no need to manufacture more rails (or more of any kind of rail) than called for the list
of required rails.

PROGRAM NAME: fence8
INPUT FORMAT
Line 1:  N (1 <= N <= 50), the number of boards 
Line 2..N+1:  N lines, each containing a single integer that represents the length of one supplied board 

Line N+2:  R (1 <= R <= 1023), the number of rails 
Line N+3..N+R+1:  R lines, each containing a single integer (1 <= ri <= 128) that represents the length of a single required fence rail 

SAMPLE INPUT (file fence8.in)
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

OUTPUT FORMAT
A single integer on a line that is the total number of fence rails that can be cut from the supplied boards. Of course, it might not be possible to cut all the possible rails from the given boards.

SAMPLE OUTPUT (file fence8.out)
7

HINTS (use them carefully!)
Fence Rails: Hint 1
This is a high dimensionality multiple knapsack problem, so we just have to test the cases. Given that the search space has a high out-degree, we will use depth first search with iterative deepening in order to limit the depth of the tree. However, straight
DFSID will be too slow, so some tree-pruning is necessary.

———————————————————
多维背包问题
使用dfs遍历,
首先把rails排序,然后,从最大的rail开始遍历。
对于第k个rail,遍历所有的板子,然后遍历地k-1个rail。如果所有的rail都有解法,则输出最开始rail。
usaco称之为DFSID

/*
ID:yunleis2
PROG:fence8
LANG:C++
*/


#include<iostream>
#include<fstream>

using namespace std;
const int MAXB=50;
const int MAXR=1024;
int boards[MAXB];
int remains[MAXB];
int rails[MAXR];
int b;
int r;
int board_sum=0;
int result=0;
int waste_max=0;
int from[MAXR];
fstream fout("fence8.out",ios::out);
inline void swap(int * a,int * b){
	int t=*a;
	*a=*b;
	*b=t;
//	*a=*a+*b;
//	*b=*a-*b;
//	*a=*a-*b;
}
int partiton(int * a,int p,int r)
{
	int x=a[r];
	int i=p-1;
	for(int j=p;j<r;j++){
		if(a[j]<x){
			++i;
			swap(a+j,a+i);
		}
	}
	swap(a+i+1,a+r);
	return i+1;
}
void quicksort(int * a,int p,int r)
{
	if(p<r)
	{
		int q=partiton(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
void dfs(int k,int waste){
	if(k<0){
		fout<<result+1<<endl;
		exit(0);
	}
	int i=0;
	if(k!=result&&rails[k]==rails[k+1])
		i=from[k+1];
	for(;i<b;i++){
		if(remains[i]>=rails[k]){
			from[k]=i;
			remains[i]-=rails[k];
			if(remains[i]<rails[0])waste+=remains[i];
			if(waste>waste_max){
				remains[i]+=rails[k];
				waste-=remains[i];
				continue;
			}
			dfs(k-1,waste);
			remains[i]+=rails[k];
		}
	}
}
int main()
{

	fstream fin("fence8.in",ios::in );
	fin>>b;
	for(int i=0;i<b;i++)
	{
		fin>>boards[i];
		board_sum+=boards[i];
		remains[i]=boards[i];
	}
	fin>>r;
	for(int i=0;i<r;i++)
		fin>>rails[i];
	quicksort(boards,0,b-1);
	quicksort(rails,0,r-1);
	int rail_sum=0;
	for(int i=0;i<r;i++){
		rail_sum+=rails[i];
		if(rail_sum>board_sum)
		{
			rail_sum-=rails[i];
			r=i;
			break;
		}
	}

	for(int i=r-1;i>=0;--i){
		result=i;
		waste_max = board_sum - rail_sum;
		rail_sum -= rails[i];
		dfs(i,0);
	}
	fout<<0<<endl;
	return 0;
}

[usaco]单源最短路径:3.3.5 Sweet Butter

http://hi.baidu.com/leokan/blog/item/3f69222ebfdbea544ec226fb.html
原文我就不贴了,直接贴另一个博客,感兴趣的可以看看这位大神的解法。
上边这个博客的作者用的是SPFA解法。
其实这道题也就是让求某几个点到其他所有的点的最短路径,我用的是Dijkstra 算法,
不过由于本题是一个非常稀疏图,使用邻接矩阵遍历的时候会非常的耗时间。
如果按普通的算法,时间复杂度在O(N^3)。
我做了一些优化,给稀疏图加上了一层索引,直接找那些相邻的边。相当于是同时使用了邻接矩阵和临界表。

看测试结果:
   Test 1: TEST OK [0.000 secs, 9632 KB]
   Test 2: TEST OK [0.000 secs, 9632 KB]
   Test 3: TEST OK [0.000 secs, 9632 KB]
   Test 4: TEST OK [0.000 secs, 9632 KB]
   Test 5: TEST OK [0.000 secs, 9632 KB]
   Test 6: TEST OK [0.027 secs, 9632 KB]
   Test 7: TEST OK [0.135 secs, 9632 KB]
   Test 8: TEST OK [0.405 secs, 9632 KB]
   Test 9: TEST OK [0.945 secs, 9632 KB]
   Test 10: TEST OK [0.891 secs, 9632 KB]
最复杂的两组结果是9和10;看出来索引对于不同分布的图性能上是有很大差别的。
看了useco的算法,是用最小化堆实现的Dijkstra算法。
我的Dijkstra算法是直接搜索最小值,因此效率是O(N);
而最小化堆,检索效率是O(1),插入删除的效率是O(logn)。由于这个查找最小值的操作位于循环内部,所以效率会有明显的提高。

rpm打包和yum安装,以及安装后自启动

rpmbuild 可以把源文件或者二进制文件打包成rpm包,rpm包可以放到源上进行分发。

执行rpmbuild –showrc  |grep topdir,可以找到rpmbuild 执行的根目录,

如果仅仅希望给把二进制文件打包成rpm包,那么把二进制文件放到  $topdir/BUILD/ 目录下。

编写${binary}.spec

Summary: client
Name: client
Version: 0.6 
Release: 1
Vendor: company
License: commercial
Group: Applications/Internet
%description
ols client
used to collect logs from client machine
%install
mkdir -p /apsara/binary
install -m 755 binary /apsara/binary
%post
/apsara/binary --_update_address=http://10.230.201.117:8080  --check_update_interval=1 --check_point_time_out=10 --send_address=http://service.ols.inc.com --domain_socket_address=/tmp/xxxxxxxxxxxxxxxxx
%files
/apsara/binary

%install 字段指的是安装rpm包时执行的命令,

%post字段值得是安装好rpm包后执行的命令。

编写好spec文件后,执行rpmbuild -bb binary.spec

就可以得到rpm包了

[usaco]4.2.1 最大流问题Drainage Ditches

 

Drainage Ditches
Hal Burch
Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s
clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.

Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Note however, that there can be
more than one ditch between two intersections.

Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

PROGRAM NAME: ditch
INPUT FORMAT
Line 1:  Two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. 
Line 2..N+1:  Each of N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate
at which water will flow through the ditch. 

SAMPLE INPUT (file ditch.in)
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

OUTPUT FORMAT
One line with a single integer, the maximum rate at which water may emptied from the pond.

SAMPLE OUTPUT (file ditch.out)
50

————————————————————————————————————–
最大流问题,按照常规算法解题即可
算法实录大致是这样的:
1:找到一个最大流路径,
2:求出其中最小的边值w;
3:把流路径上的每一条边减去w,并反向增加一条w的边。
4:重复1-3,直到找不到这样的一条路径为止。

找最大流路径的算法使用变形的dijeskal算法。

/*
ID:yunleis2
PROG:ditch
LANG:C++
*/

#include<iostream>
#include<fstream>

using namespace std;

const int MAXN=201;
const int MAXM=201;
int N;
int M;
int metri[MAXM][MAXM];
int prevs[MAXM];
int length[MAXM];
bool visited[MAXM];
int main()
{
	fstream fin("ditch.in",ios::in);
	fin>>N>>M;
	for(int i=0;i<N;i++){
		int a,b,c;
		fin>>a>>b;
		fin>>c;
		metri[a][b]+=c;
	}
	int total=0;
	int flag=true;
	while(flag){
		//disjeskal to find a max flow;
		for(int i=1;i<=M;i++){
			length[i]=metri[1][i];//-metri[i][1];
			prevs[i]=1;
			visited[i]=false;
		}
		prevs[1]=0;
		visited[1]=true;
		while(true){
			int ptr=1;
			int maxflow=0;
			for(int i=1;i<=M;i++){
				if(!visited[i]&&length[i]>maxflow){
					maxflow=length[i];
					ptr=i;
				} 
			}
			if(maxflow<=0)
			{	
				flag=false;
				break;
			}
			visited[ptr]=true;
			if(ptr==M){
				int ptr1=ptr;
				int minflow=1000000;
				while(ptr1!=1){
					if((metri[prevs[ptr1]][ptr1]/*-metri[ptr1][prevs[ptr1]]*/)<minflow)
						minflow=metri[prevs[ptr1]][ptr1];//-metri[ptr1][prevs[ptr1]];
					ptr1=prevs[ptr1];
				}
				ptr1=ptr;
				while(ptr1!=1){
					metri[prevs[ptr1]][ptr1]-=minflow;
					metri[ptr1][prevs[ptr1]]+=minflow;
					ptr1=prevs[ptr1];
				} 
				total+=minflow;
				break;
			}
			for(int i=1;i<=M;i++){
				if(!visited[i]&&(metri[ptr][i]/*-metri[i][ptr]*/)>length[i]){
					length[i]=metri[ptr][i];//-metri[i][ptr];
					prevs[i]=ptr;
				}
			}

		}
	}
	fstream fout("ditch.out",ios::out);
	fout<<total<<endl;
	//system("pause");

} 
 

USER: Ma yunlei [yunleis2] TASK: ditch LANG: C++

Compiling... Compile: OK

Executing...    Test 1: TEST OK [0.000 secs, 3184 KB]    Test 2: TEST OK [0.000 secs, 3184 KB]    Test 3: TEST OK [0.000 secs, 3184 KB]    Test 4: TEST OK [0.000 secs, 3184 KB]    Test 5: TEST OK [0.000 secs, 3184 KB]    Test 6: TEST OK [0.000 secs, 3184 KB]    Test 7: TEST OK [0.000 secs, 3184 KB]    Test 8: TEST OK [0.000 secs, 3184 KB]    Test 9: TEST OK [0.000 secs, 3184 KB]    Test 10: TEST OK [0.000 secs, 3184 KB]    Test 11: TEST OK [0.000 secs, 3184 KB]    Test 12: TEST OK [0.000 secs, 3184 KB]

All tests OK. YOUR PROGRAM ('ditch') WORKED FIRST TIME!  That's fantastic -- and a rare thing.  Please accept these special automated congratulations.

 

使用wordpress搭建博客过程中遇到的一些问题

对于一个新手而言,第一次使用wordpress搭建个人博客,而且要在不同的环境上work,包括mac,ubuntu。再搭建的过程中遇到了很多的问题,通过一步步调试,逐步定位

问题所。

比如wordpress在上传图片的时候会自动生成缩略图,这个在mac上工作的很好,但是移植到ubuntu上的时候,缩略图生成不了了。

通过一步步添加日志的方法,逐步定位到是因为ubuntu上的php没有安装gd扩展。

下边提供一种定位的方法:

打印调用栈:在你的代码中调用这段代码,就能看到完整的调用栈。这对你整理程序的逻辑非常有好处。

function print_stack_trace()

{

    $array
=debug_backtrace();

   unset($array[0]);

   foreach($array
as $row)

    { 

       $html
.=$row[file].:.$row[line].
line; fun::.$row[function].\n“;

    }

    error_log($html);

}

——————

时间比较紧,没太多时间整理文章,想到什么就说什么了,只是为了记录这些辛辛苦苦得来的经验,方便后来者少走弯路。

巧妙的设计stl中的比较函数,以避免不必要的cpu开销

在stl algorithm.h中,常利用一些排序操作,比如通过vector实现一个堆。
如果堆的每个元素是自定义结构,也就是,自己实现的类作为堆的基本元素,
那么make_heap和push_heap,pop_heap就需要开发者提供自己的比较函数。
bool __cmp(value &v1 ,value & v2).
在stl的内部实现中,当这个_cmp判定为true时,就需要调整heap,所以如果
v1 == v2 返回 true。那么恭喜你,掉进了坑里。如果返回false,则能够节省不小的开销,尤其当你的堆用在一个循环内的时候。

ps.在stl中类似heap的结构,最好使用指针作为基本元素,否则数据调整的时候,
拷贝的量是很大的。

[usaco]4.2.2偶图匹配 The Perfect Stall

The Perfect Stall
Hal Burch
Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but
it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and,
of course, a cow may be only assigned to one stall.

Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.

PROGRAM NAME: stall4
INPUT FORMAT
Line 1:  One line with two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. 

Line 2..N+1:  N lines, each corresponding to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing
to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow. 

SAMPLE INPUT (file stall4.in)
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

OUTPUT FORMAT
A single line with a single integer, the maximum number of milk-producing stall assignments that can be made.

SAMPLE OUTPUT (file stall4.out)
4

—————————————————–
典型的偶图匹配问题

初始化是,把无向图转换成有向图,每一条无向边转化成从stall到cow的边。
之后进行匹配
如果cow和一个stall进行了匹配,那么把cow到stall的边转化成从cow到stall的边。

进行匹配的过程如下。
如果一个还没有匹配的cow和一个stall,之间有一条交互路径,那么把这条交互路径上的所有的边进行转向。。
同时加入这个cow和stall。
当搜索不到这样的路径时,搜索结束。

/*
ID:yunleis2
PROG:stall4
LANG:C++
*/

#include<iostream>
#include<fstream>

using namespace std;
const int maxn=201;
const int maxm=201;
int n,m;
int  metri[maxn][maxm];
bool cow[maxn];
int cownext[maxm];
int stallnext[maxn];
bool stall[maxm];
bool cowvisited[maxn];
bool search(int p);
int main()
{
	fstream fin("stall4.in",ios::in );
	fin>>n>>m;
	for(int i=1;i<=n;i++){
		int a,b;
		fin>>a;
		for(int j=0;j<a;j++){
			fin>>b;
			metri[i][b]=1;
		}
	}

	while(true){
		bool flag=false;
		for(int s=1;s<=n;s++)
			cowvisited[s]=false;
		for(int i=1;i<=m;i++){
			if(!stall[i]){
				
				if(search(i))
				{
					flag=true;
					stall[i]=true;
					//--i;continue;
				}
				 
			}
		}
		if(!flag)
			break;		 
	}
	int result=0;
#if 0
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<metri[i][j]<<" ";
		}
		cout<<endl;
	}
#endif
	for(int i=1;i<=n;i++){
		if(cow[i])
			result++;
	}
	fstream fout("stall4.out",ios::out);
	fout<<result<<endl;
	//system("pause");
}
bool search(int p){
	//stall p;
	for(int i=1;i<=n;i++){
		if(cowvisited[i])
			continue;
		if(metri[i][p]==1){
			
			if(!cow[i]){
				cow[i]=true;
				cownext[i]=p;
				metri[i][p]=2;
				cowvisited[i]=true;
				return true;
			}
			else if(metri[i][cownext[i]]==2){
				cowvisited[i]=true;
				bool flag=search(cownext[i]);
				if(flag){
					metri[i][p]=2;
					metri[i][cownext[i]]=1;
					cownext[i]=p;
					return flag;
				}
			}
		}
	}
	return false;
}

 

 

 

[usaco] 4.4.1PROB Shuttle Puzzle

 
Shuttle Puzzle
Traditional
The Shuttle Puzzle of size 3 consists of 3 white marbles, 3 black marbles, and a strip of wood with 7 holes. The marbles of the same color are placed in the holes at the opposite ends of the strip, leaving the center hole empty.

INITIAL STATE: WWW_BBB
GOAL STATE: BBB_WWW

To solve the shuttle puzzle, use only two types of moves. Move 1 marble 1 space (into the empty hole) or jump 1 marble over 1 marble of the opposite color (into the empty hole). You may not back up, and you may not jump over 2 marbles.

A Shuttle Puzzle of size N consists of N white marbles and N black marbles and 2N+1 holes.

Here’s one solution for the problem of size 3 showing the initial, intermediate, and end states:

WWW BBB
WW WBBB
WWBW BB
WWBWB B
WWB BWB
W BWBWB
 WBWBWB
BW WBWB
BWBW WB
BWBWBW
BWBWB W
BWB BWW
B BWBWW
BB WBWW
BBBW WW
BBB WWW

Write a program that will solve the SHUTTLE PUZZLE for any size N (1 <= N <= 12) in the minimum number of moves and display the successive moves, 20 per line.

PROGRAM NAME: shuttle
INPUT FORMAT
A single line with the integer N.
SAMPLE INPUT (file shuttle.in)
3

OUTPUT FORMAT
The list of moves expressed as space-separated integers, 20 per line (except possibly the last line). Number the marbles/holes from the left, starting with one.

Output the the solution that would appear first among the set of minimal solutions sorted numerically (first by the first number, using the second number for ties, and so on).

SAMPLE OUTPUT (file shuttle.out)
3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

 

——————————————————————————–
好奇怪的一道题。

主要算法是bfs。
主要有四种情况需要处理。
W_B->_WB
W_B->WB_
_WB->BW_
WB_->_BW
所以对于一个状态,只需要处理这四种情况就可以了。
不过好奇怪,我把hash开得很大的时候,说资源超限,然后改小了,奇迹般的过了。
但是对于超过10的情况,我的机器还是跑不出来(超过了5s),不知道usaco是什么样的神奇的机器,竟然可以在0.几秒内跑出来。

USER: Ma yunlei [yunleis2]
TASK: shuttle
LANG: C++

Compiling…
Compile: OK

Executing…
   Test 1: TEST OK [0.000 secs, 3376 KB]
   Test 2: TEST OK [0.000 secs, 3376 KB]
   Test 3: TEST OK [0.000 secs, 3376 KB]
   Test 4: TEST OK [0.000 secs, 3376 KB]
   Test 5: TEST OK [0.000 secs, 3376 KB]
   Test 6: TEST OK [0.000 secs, 3384 KB]
   Test 7: TEST OK [0.000 secs, 3384 KB]
   Test 8: TEST OK [0.027 secs, 3384 KB]
   Test 9: TEST OK [0.108 secs, 3384 KB]
   Test 10: TEST OK [0.243 secs, 3384 KB]

All tests OK.
Your program (‘shuttle’) produced all correct answers!  This is your
submission #6 for this problem.  Congratulations!

Here are the test data inputs:

——- test 1 —-
1
——- test 2 —-
3
——- test 3 —-
4
——- test 4 —-
5
——- test 5 —-
7
——- test 6 —-
8
——- test 7 —-
9
——- test 8 —-
10
——- test 9 —-
11
——- test 10 —-
12

 

/*
ID:yunleis3
PROG:shuttle
LANG:C++
*/
#include <fstream>

#include<iostream>
#include<queue>
using namespace std;

const int maxn=13;
int n;
const int black=3;
const int white=2;
const int blank=1;
const int maxnhash=167216;
bool hash1[maxnhash];
bool hash2[maxnhash];

unsigned long
	elf_hash(const char *name)
{
	unsigned long       h = 0, g;

	while (*name) {
		h = (h << 4) + *name++;
		if (g = h & 0xf0000000)
			h ^= g >> 24;
		h &= ~g;
	}
	return h;
}
class step{
public :
	queue<int> steps;
	char state[2*maxn+1];
	int ptr;
	step  operator =(step &s){
		steps=s.steps;
		for(int i=0;i<=2*n+1;++i){
			this->state[i]=s.state[i];
		}
		return * this;
	}
};
inline void swap(char *a,char *b){
	char x=*a;
	*a=*b;
	*b=x;
}

inline void  myhash(const char * ch,unsigned &ha1,unsigned ha2){
	unsigned result=0;
	int end=2*n+1;
	ha1=0;
	for(int i=0;i<n;++i){
		ha1<<=2;
		ha1+=ch[i];
	}
	ha2=0;
	for(int i=n;i<end;++i){
		ha2<<=2;
		ha2+=ch[i];
	} 
}
int main(){
	ifstream fin("shuttle.in");
	fin>>n;
	step init;
	step rs;
	queue<step> result;
	for(int i=0;i<n;i++){
		init.state[i]=white;
	}
	init.state[n]=blank;
	for(int i=n+1;i<2*n+1;i++){
		init.state[i]=black;
	}
	init.ptr=n;
	init.state[2*n+1]='\0';
	queue<step> q;
	q.push(init);
	
	while(!q.empty()){
		step s=q.front();
		q.pop();
		//check
 
		 
		static unsigned h1;
		static unsigned h2;
		myhash(s.state,h1,h2);
		h1%=maxnhash;
		h2%=maxnhash;
		if(hash1[h1]&&hash2[h2])
		{
			//cout<<"mark"<<endl;;
			continue;
		}
		hash1[h1]=true;
		hash1[h2]=true;
		if(s.ptr==n){
			bool flag=true;
			for(int i=0;flag&&i<n;i++){
				if(s.state[i]==white)
					flag=false;
			}			
			for(int i=n+1;flag&&i<2*n+1;i++){
				if(s.state[i]==black)
					flag=false;
			}
			if(flag){
				rs=s;//result.push(s);
				break;
			}
		}
		if((s.ptr-1)>=0&&s.state[s.ptr-1]==white){
			step s1=s;
			swap(s1.state+s1.ptr-1,s1.state+s1.ptr);
			--s1.ptr;
			s1.steps.push(s1.ptr);
			q.push(s1);
		}
		if((s.ptr-2)>=0&&s.state[s.ptr-2]==white&&s.state[s.ptr-1]==black){
			step s2=s;
			swap(s2.state+s2.ptr-2,s2.state+s2.ptr);
			--(--s2.ptr);
			s2.steps.push(s2.ptr);
			q.push(s2);
		}
		if((s.ptr+1)<(2*n+1)&&s.state[s.ptr+1]==black){
			step s3=s;
			swap(s3.state+s3.ptr+1,s3.state+s3.ptr);
			++s3.ptr;
			s3.steps.push(s3.ptr);
			q.push(s3);
		}
		if((s.ptr+2)<(2*n+1)&&s.state[s.ptr+2]==black&&s.state[s.ptr+1]==white){
			step s4=s;
			swap(s4.state+s4.ptr+2,s4.state+s4.ptr);
			++(++s4.ptr);
			s4.steps.push(s4.ptr);
			q.push(s4);
		}
	}
	
	
	queue<int> q1=rs.steps;
	int ptr=0;
	ofstream fout("shuttle.out");
	while(!q1.empty()){
		fout<<q1.front()+1;//<<" ";
		q1.pop();
		if(q1.empty())
			break;
		if((++ptr)==20)
		{	fout<<endl;
			ptr=0;
		}
		else
			fout<<" ";
		
	}
	fout<<endl;
	//system("pause");
}

[usaco]Bessie Come Home

Kolstad & Burch
It’s dinner time, and the cows are out in their separate pastures. Farmer John rings the bell so they will start walking to the barn. Your job is to figure out which one cow gets to the barn first (the supplied test data will always have exactly one fastest
cow).

Between milkings, each cow is located in her own pasture, though some pastures have no cows in them. Each pasture is connected by a path to one or more other pastures (potentially including itself). Sometimes, two (potentially self-same) pastures are connected
by more than one path. One or more of the pastures has a path to the barn. Thus, all cows have a path to the barn and they always know the shortest path. Of course, cows can go either direction on a path and they all walk at the same speed.

The pastures are labeled `a’..`z’ and `A’..`Y’. One cow is in each pasture labeled with a capital letter. No cow is in a pasture labeled with a lower case letter. The barn’s label is `Z’; no cows are in the barn, though.

PROGRAM NAME: comehome
INPUT FORMAT
Line 1:  Integer P (1 <= P <= 10000) the number of paths that interconnect the pastures (and the barn) 

Line 2..P+1:  Space separated, two letters and an integer: the names of the interconnected pastures/barn and the distance between them (1 <= distance <= 1000) 

SAMPLE INPUT (file comehome.in)
5
A d 6
B d 3
C e 9
d Z 8
e Z 3

OUTPUT FORMAT
A single line containing two items: the capital letter name of the pasture of the cow that arrives first back at the barn, the length of the path followed by that cow.

SAMPLE OUTPUT (file comehome.out)
B 11

——————————————————————–
本题就是一个拓扑排序,找到到根节点最近的带权节点。
由于最多有26×2=52个节点。因此直接用关联矩阵就可以了。

 

 

 

我的解法:
——————————————————————————————————————————————————————————

/*
ID:yunleis2
PROG:comehome
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
int src[26*2][26*2];
int dest[26*2];
int main()
{
	fstream fin("comehome.in",ios::in);
	int p;
	fin>>p;
	for(int i=0;i<52;i++)
	{
		for(int j=0;j<52;j++)
		{
			src[i][j]=-1;
			
			if(i==j)
			{
				src[i][j]=0;
				 
			}
		}
		dest[i]=-1;
	}

	queue<int > q;
	dest['Z'-'A']=0;
	for(int i=0;i<p;i++)
	{
		char a,b;
		int w;
		fin>>a>>b>>w;
		if(a>='a')
			a=a-'a'+'A'+26;
		if(b>='a')
			b=b-'a'+'A'+26;
		if(src[a-'A'][b-'A']==-1||src[a-'A'][b-'A']>w)
		{
			src[a-'A'][b-'A']=w;
			src[b-'A'][a-'A']=w;
		}
	}
 /*
	for(int i=0;i<52;i++)
	{
		for(int j=0;j<52;j++)
		{
			if(i!=j&&src[i][j]!=-1)
				cout<<i<<"\t"<<j<<"\t"<<src[i][j]<<endl;
		}
	}
 */
	q.push('Z'-'A');
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=0;i<52;i++)
		{
			if(src[t][i]!=-1&&(dest[i]==-1||( (src[t][i]+dest[t])<dest[i] )))
			{
				dest[i]=src[t][i]+dest[t];
				q.push(i);
			}
		}

	}
	int ptr=-1;
	for(int i=0;i<26;i++)
	{
		if(dest[i]>0)
		{
			cout<<i<<" "<<dest[i]<<endl;
			if(ptr==-1)
				ptr=i;
			else
				if(dest[i]<dest[ptr])
					ptr=i;
		}
	}
	fstream fout("comehome.out",ios::out);
	fout<<(char)('A'+ptr)<<" "<<dest[ptr]<<endl;
// 	system("pause");
}

 

[usaco]Agri-Net(使用最小生成树算法)

Agri-Net
Russ Cox
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.

Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.

Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.

The distance between any two farms will not exceed 100,000.

PROGRAM NAME: agrinet
INPUT FORMAT
Line 1:  The number of farms, N (3 <= N <= 100). 
Line 2..end:  The subsequent lines contain the N x N connectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some
lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem. 

SAMPLE INPUT (file agrinet.in)
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

OUTPUT FORMAT
The single output contains the integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

SAMPLE OUTPUT (file agrinet.out)
28

——————
这个问题就是让求最小生成树。
利用prim 算法,或者kruskal算法即可。
鉴于节点的总个数小于等于100,可以使用一个常量数组
我的解法
—————-

/*
ID:yunleis2
PROG:agrinet
LANG:C++
*/
#include<iostream>
#include<fstream>

using namespace std;
/************************************************************************/
/* minimal spinning tree                                                                     */
/************************************************************************/
int metri[101][101];
int destance[101]; 
bool intree[101];
int main()
{
	fstream fin("agrinet.in",ios::in);
	int N;
	fin>>N;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)	
		{
			fin>>metri[i][j];
		}
		destance[i]=0;
		intree[i]=false;
	}
	int sum=0;
	for(int i=0;i<N;i++)
	{
		if(!intree[i])
		{
			intree[i]=true;
			for(int j=0;j<N;j++)
			{
				destance[j]=metri[i][j];
			}
			while(true)
			{
				int ptr=-1;
				for(int j=0;j<N;j++)
				{
					if(ptr==-1||destance[ptr]==0||(intree[ptr]))
						ptr=j;
					else if((!intree[j])&&destance[j]<destance[ptr])
						ptr=j;
				}
				if(intree[ptr])
					break;
				intree[ptr]=true;
				sum+=destance[ptr];
				for(int j=0;j<N;j++)
				{
					if((!intree[j])&&(destance[j]>metri[ptr][j]))
					{
						destance[j]=metri[ptr][j];
					}
				}
			}
		}
	}
	fstream fout("agrinet.out",ios::out);
	fout<<sum<<endl;
	//system("pause");

}

测试:

USER: Ma yunlei [yunleis2]
TASK: agrinet
LANG: C++

Compiling…
Compile: OK

Executing…
   Test 1: TEST OK [0.000 secs, 3064 KB]
   Test 2: TEST OK [0.000 secs, 3064 KB]
   Test 3: TEST OK [0.000 secs, 3064 KB]
   Test 4: TEST OK [0.000 secs, 3064 KB]
   Test 5: TEST OK [0.000 secs, 3064 KB]
   Test 6: TEST OK [0.000 secs, 3064 KB]
   Test 7: TEST OK [0.000 secs, 3064 KB]
   Test 8: TEST OK [0.000 secs, 3064 KB]
   Test 9: TEST OK [0.000 secs, 3064 KB]
   Test 10: TEST OK [0.000 secs, 3064 KB]

All tests OK.
YOUR PROGRAM (‘agrinet’) WORKED FIRST TIME!  That’s fantastic
— and a rare thing.  Please accept these special automated
congratulations.