USACO算法系列二十六——fence6

    題目：http://www.nocow.cn/index.php/Translate:USACO/fence6

    找周長最小的多邊形。使用的還是深度周遊，剪枝的方法。

    #include<iostream>

#include <fstream>

#define ESIZE 8

#define SIZE 101

#define LARGENUMBER 0X7FFFFFFF

using namespace std;

struct Edge

{

int s; //标号

int ls; //邊的長度

int n1s; //端點一的邊數

int n1array[ESIZE];

int n2s; //端點二的邊數

int n2array[ESIZE];

};

int n=0; //邊

Edge edge[SIZE];

int result = LARGENUMBER;

int isuse[SIZE] = {0};

ifstream fin("fence6.in");

ofstream fout("fence6.out");

//是否是

bool ispoint1(int now, int last)

{

for (int i=0; i < edge[now].n1s; i ++)

{

if (edge[now].n1array[i] == last)

{

return true;

}//end if

}//end for

return false;

}

//深度周遊搜尋解

void fence(int start, int last, int now, int load)

{

//剪枝

if (load >= result)

{

return;

}

else

{

int * p;

int length;

if (ispoint1(now, last))

{

p = edge[now].n2array;

length = edge[now].n2s;

}//end if ispoint1

else

{

p = edge[now].n1array;

length = edge[now].n1s;

}//end if...else..

load += edge[now].ls;

isuse[now] = 1;

for (int i=0; i < length; i ++ )

{

int index = edge[p[i]].s;

if (index == start )

{

if (ispoint1(start, now))

{

result = result < load ? result : load;

}//end if

}//end 形成閉合的路徑

else

{

if (isuse[index] == 0)

{

fence(start, now, index, load);

}

}//遞歸

}//end for

isuse[now] = 0;

}//end else

}

int main()

{

//輸入資料

fin >> n;

for (int i=0; i < n; i ++)

{

int index ;

fin >> index;

edge[index].s = index;

fin>>edge[index].ls >> edge[index].n1s >> edge[index].n2s;

//輸入端點1的邊數

for (int j=0; j < edge[index].n1s; j ++)

{

fin >> edge[index].n1array[j];

}

//輸入端點2的邊數

for (int j=0; j< edge[index].n2s; j ++)

{

fin >> edge[index].n2array[j];

}//end for 2

}//end for i

for(int i=1; i < SIZE; i ++)

{

if (edge[i].s == i)

{

for (int j =0; j < edge[i].n2s; j ++)

{

isuse[i] = 1;

fence(i, i, edge[i].n2array[j], edge[i].ls);

}//end for j

}//end if

}//end for i

fout<< result <<endl;

return 0;

}

    發現自己的回溯法，使用的有點心得了，哈哈……再接再厲，一遍就AC了。

    Executing...

Test 1: TEST OK [0.000 secs, 3024 KB]

Test 2: TEST OK [0.000 secs, 3024 KB]

Test 3: TEST OK [0.000 secs, 3024 KB]

Test 4: TEST OK [0.011 secs, 3024 KB]

Test 5: TEST OK [0.000 secs, 3024 KB]

Test 6: TEST OK [0.011 secs, 3024 KB]

Test 7: TEST OK [0.011 secs, 3024 KB]

Test 8: TEST OK [0.000 secs, 3024 KB]

Test 9: TEST OK [0.000 secs, 3024 KB]

All tests OK.

YOUR PROGRAM ('fence6') WORKED FIRST TIME! That's fantastic

-- and a rare thing. Please accept these special automated

congratulations.

    太感動了。^_^