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

Fence Rails
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

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.

———————————————————

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

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]

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

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

```Summary: client
Name: client
Version: 0.6
Release: 1
Vendor: company
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
%files
/apsara/binary
```

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

%post字段值得是安装好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，直到找不到这样的一条路径为止。

```/*
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]
LANG: C++Compiling...
Compile: OKExecuting...
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搭建博客过程中遇到的一些问题

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实现一个堆。

bool __cmp(value &v1 ,value & v2).

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

—————————————————–

```/*
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
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

——————————————————————————–

W_B->_WB
W_B->WB_
_WB->BW_
WB_->_BW

USER: Ma yunlei [yunleis2]
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.
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

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

——————————————————————–

——————————————————————————————————————————————————————————

```/*
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

——————

—————-

```/*
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]
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.