2017中興アルゴリズムチャレンジ試合
， ，46 ， “ ， ， ”，GG， ， ~
：
， ！ ， ， 。 ， ， ， 。 ， 、 （ ）。 ， ， ： ， ， ， 。 ， ： ， ， ， ：
1. ， （ ）；
2. ， 9 （ ， ）；
3. ， ， （ ）；
4. ， ， ， ！ （ ）；
5. ， ， ， ( )。
， , 。 ？ ， ， ， ！ ， ， ， ， ？
：
1、 ， （ ）， ( );
2、 ；
3、 ， ， ， ；
4、 S E 。
5、 ： 。
：
， + ， ， ， ， ，
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define EPS 1e-8
#define alfa 1.0 // ，
double beta = 0.8; // ，
#define rou 0.4 //
double Q = 30.0; //
const int MAXN = 2000;// 200
const int INF = 100000;
int edgenum = 0;
int nodes, edges;
int startnode, endnode;// ，
clock_t start, end;
vector>a(MAXN, vector(MAXN, INF));
struct edge
{
int u;
int v;
int cost;
int next;
}e[300000], e1[300000];
struct Node
{
int index;
int value;
};
struct Way
{
int waynodes;//
int waycost;
vectorway;
};
int first[MAXN];
int first1[MAXN];
vectormustnodes;//
vectorismustnode;
vector>mustedges;//
vectormustedge;
vectorfather;
vector>notedges;//
vectorvirtualnode;
setmustvirtualnode;
vector>>tao;
void add(int u, int v, int cost)
{
e[edgenum].u = u;
e[edgenum].v = v;
e[edgenum].cost = cost;
e[edgenum].next = first[u];
int cur = edgenum;
first[u] = edgenum++;
//cout << "edgenum=" << cur << " u=" << u << " v=" << v<&nodes, int &v)
{
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i].value == v)return i;
}
return -1;
}
void show(vector&v)
{
for (int i = 0; i < v.size(); i++) cout << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(4) << v[i];
cout << endl;
}
void show(vector>&v)
{
for (int i = 0; i < v.size(); i++)
{
for (int j = 0; j < v[i].size(); j++)cout << v[i][j] << " ";
cout << endl;
}
}
void show(vector&v)
{
for (int i = 0; i < v.size(); i++)cout << "index=" << v[i].index << " " << v[i].value << endl;
}
void GetPath2(int &newindex, int &s, vector&oldtonew, vector>>&map)
{
int n = nodes;
vectordist(n, INF);
vectorpdist(n, INF);
vector>pre(n, vector(n, -1));
vectorpath;
vectormin(n, INF);
dist[s] = 0;
/*for (int i = first[s]; i != -1; i = e[i].next)
{
int u = e[i].u;
int v = e[i].v;
dist[v] = e[i].cost;
pre[0][v] = s;
}*/
pdist = dist;
//m_mincost[0] = dist[t];
int m = 0;
//show(dist);
while (1)
{
//cout << "m=" << m << endl;
pdist = dist;
for (int i = 0; i < n; i++)
{
for (int k = first[i]; k != -1; k = e[k].next)
{
int u = e[k].u;
int v = e[k].v;
//cout << "u=" << u << " v=" << v << endl;
if (pdist[v] + e[k].cost < dist[u])
{
//cout << "i1=" << u << " j1=" << v << endl;
dist[u] = pdist[v] + e[k].cost;
pre[m][u] = v;
//show(dist);
}
}
if (i != s)
{
if (s == 0 && i == endnode)break;
int index = oldtonew[i];
//cout << "index0=" << index << endl;
if (index != -1 && pre[m][i] != -1 && dist[i]>>map(k, vector>(k));
int count = 0;
double num = 0, cost = 0;
int s = 0;
//show(oldtonew);
//cout << "father" << endl;
//show(ismustnode);
//maxdeep(s, mustgo);
//GetPath(s, s, maxdeep(s, mustgo)-1, mustgo, map);
father = oldtonew;
//show(father);
for (int i = 0; i < k-1; i++)
{
int u = mustgo[i].value;
int maxnodes = 0;
GetPath2(i, u, oldtonew, map);
}
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
if (i == j)continue;
vectorway = map[i][j];
/*if (way.size() == 0)
{
cout << "i=" << i << " j=" << j << endl;
}*/
for (int i0 = 0; i0 < way.size(); i0++)
{
count++;
Way temp = way[i0];
num = num + temp.waycost;
//cost = cost + temp.waynodes;
//cout << "way cost=" << way[i0].waycost << endl;
//show(way[i0].way);
}
}
}
double temp = 1.0*num + 1.0*cost;
temp = temp / count;
cout << "temp=" << temp << endl;
beta = 3.0;
//return mustgo;
}
void Init_S(vector>>&map)
{
int len = map.size();
vector>>temp(len, vector>(len));
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
int tlen = map[i][j].size();
vectortemp0(tlen, 0.0);
temp[i][j] = temp0;
}
}
tao = temp;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
vectorway = map[i][j];
if (way.size()>0)
{
for (int k = 0; k < way.size(); k++)
{
tao[i][j][k] = 1.0 / way.size();
if (way[k].way.size() == 2)
{
int u = way[k].way[0];
int v = way[k].way[1];
int k1 = findmustedges(u);
int k2 = findmustedges(v);
if (i != j && (k1 == k2) && (k1 != -1 && k2 != -1))
{
//cout << "i=" << i << " j=" << j << endl;
//cout << "u=" << u << " v=" << v << " k=" << k << endl;
tao[i][j][k] = INF;
}
}
}
}
}
}
}
class Ant
{
public:
int N;
int Cost;
vectorOrder;
vectorPath;
vectorAllowedCity;
vectorChooseIndex;
int CurCity;
int MovedCityCount;
Ant(int N)
{
this->N = N;
this->Init();
}
void Init()
{
Cost = 0;
vector_Order;
vector_AllowedCity(N, 1);
vector_ChooseIndex(N, -1);
CurCity = 0;
MovedCityCount = 1;
Order = _Order;
AllowedCity = _AllowedCity;
ChooseIndex = _ChooseIndex;
Path.clear();
Order.push_back(0);
AllowedCity[0] = 0;
}
};
int choose(vectorv)
{
static int num = 0;
srand(unsigned(time(0)) + num);
num = rand();
int len = v.size();
vectorq(len + 1, 0.0);
double sum = 0;
int index = 0;
for (int i = 0; i < len; i++)
{
sum = sum + v[i];
}
//cout << "sum=" << sum << endl;
for (int i = 0; i < len; i++)
{
v[i] = v[i] * 1.0 / sum;
q[i + 1] = q[i] + v[i];
}
//for (int i = 0; i < v.size(); i++)cout << v[i] << " ";
//cout << endl;
double rd = rand() / (RAND_MAX + 1.0);
//for (int i = 0; i < q.size(); i++)cout << q[i] << " ";
//cout << endl;
//cout << rd << endl;
while (1)
{
rd = rand() / (RAND_MAX + 1.0);
index = 0;
while (q[index] < rd)
{
index++;
}
index--;
//rd = rand() / (RAND_MAX + 1.0);
if (index >= 0)break;
}
/*while (1)
{
rd = rand() / (RAND_MAX + 1.0);
int low = 0, high = len;
while (low < high)
{
if (q[low] < rd&&rd < q[low + 1])break;
int middle = (high - low) / 2 + low;
if (rd < q[middle])high = middle;
else if (rd > q[middle])low = middle;
}
low--;
index = low;
if (index>= 0)break;
}*/
return index;
}
void updatetrial2(vector>>&map, vector&Ants, int &curcost ,int &bestcost, int &maxnode)
{
static int num1 = 0;
srand(unsigned(time(0)) + num1);
num1 = rand();
int antsize = Ants.size();
int len = map.size();
vector>>Temptao(len, vector>(len, vector(len, 0.0)));
vectorpt(Ants.size(), 0.0);
//cout << "curcost=" << curcost << " bestcost=" << bestcost << endl;
vectorcould(pt.size(), 0);
for (int i = 0; i < Ants.size(); i++)
{
if (Ants[i].Path.size() <= maxnode)
{
pt[i] = Ants[i].Path.size()*0.6 + Ants[i].Cost*0.4;
pt[i] = 3.0 / pt[i];
could[i] = 1;
}
else
{
if (rand() % 2 == 0)
{
if (Ants[i].Cost <= bestcost)
{
pt[i] = Ants[i].Path.size()*0.6 + Ants[i].Cost*0.4;
pt[i] = 1.0 / pt[i];
could[i] = 1;
}
}
else
{
if (Ants[i].Cost <= curcost)
{
pt[i] = Ants[i].Path.size()*0.6 + Ants[i].Cost*0.4;
pt[i] = 1.0 / pt[i];
could[i] = 1;
}
}
}
}
//for (int i0 = 0; i0 < antsize; i0++)
//for (int i = 0; i < pt.size(); i++)cout << could[i] << " ";
//cout << endl;
for (int i0 = 0; i0 < Ants.size(); i0++)
{
int i = i0;
if (could[i] == 0)continue;
//i = choose(pt);
//cout << "i=" << i << " cost=" << Ants[i].Cost << endl;
//cout << "order" << endl;
//show(Ants[i].Order);
for (int j = 1; j < Ants[i].Order.size(); j++)
{
int m = Ants[i].Order[j];
int n = Ants[i].Order[j - 1];
//cout << "i=" << i << " j=" << j << endl;
//cout << "m=" << m << " n=" << n << endl;
vectorway = map[m][n];
//cout << "size=" << way.size() << endl;
int index = Ants[i].ChooseIndex[m];
if (way.size()>0)
{
//for (int k = 0; k < way.size(); k++)
{
//cout << "update=" << index << endl;
Temptao[n][m][index] = Temptao[n][m][index] + Q / (Ants[i].Path.size()*0.0 + Ants[i].Cost*1.0);
Temptao[m][n][index] = Temptao[n][m][index];
}
}
}
}
//for (int i0 = 0; i0 < Ants.size()/2; i0++)
//{
// int i = i0;
// i = choose(pt);
// //cout << "i=" << i << " cost=" << Ants[i].Cost << endl;
// for (int j = 1; j < len; j++)
// {
// int m = Ants[i].Order[j];
// int n = Ants[i].Order[j - 1];
// //cout << "i=" << i << " j=" << j << endl;
// //cout << "m=" << m << " n=" << n << endl;
// vectorway = map[m][n];
// //cout << "size=" << way.size() << endl;
// int index = Ants[i].ChooseIndex[m];
// if (way.size()>0)
// {
// //for (int k = 0; k < way.size(); k++)
// {
// //cout << "update=" << index << endl;
// Temptao[n][m][index] = Temptao[n][m][index] + Q / (Ants[i].Path.size()*0.0 + Ants[i].Cost*1.0);
// Temptao[m][n][index] = Temptao[n][m][index];
// }
// }
// }
//}
//cout << "here update" << endl;
double maxconcentration = 0;
double a = 0.1;
double tmax = 10, tmin = 1;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
vectorway = map[i][j];
if (way.size()>0)
{
for (int k = 0; k < way.size(); k++)
{
tao[i][j][k] = tao[i][j][k] * rou + Temptao[i][j][k];
if (way[k].way.size() == 2)
{
int u = way[k].way[0];
int v = way[k].way[1];
int k1 = mustedge[u];
int k2 = mustedge[v];
if (i != j && (k1 == k2) && (k1 != -1 && k2 != -1))
{
tao[i][j][k] = INF;
}
else
{
if (tao[i][j][k] >= tmax)tao[i][j][k] = tmax;
maxconcentration = maxconcentration>tao[i][j][k] ? maxconcentration : tao[i][j][k];
}
}
else
{
if (tao[i][j][k] >= tmax)tao[i][j][k] = tmax;
maxconcentration = maxconcentration > tao[i][j][k] ? maxconcentration : tao[i][j][k];
}
}
}
}
}
//cout << "max=" << maxconcentration << endl;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
for (int k = 0; k < tao[i][j].size(); k++)
{
if (tao[i][j][k] < 0.1*maxconcentration)
{
tao[i][j][k] = 0.1*maxconcentration;
}
}
}
}
}
void check(vector&path)//
{
int mustnodesum = mustnodes.size();
int mustedgesum = mustedges.size();
for (int i = 0; i < path.size(); i++)
{
if (ismustnode[path[i]] != -1)
{
cout << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(4) << path[i];
mustnodesum--;
ismustnode[path[i]] = -1;
}
}
cout << endl;
cout << "the number of non visited necessary nodes "< 0)
{
cout << "error path" << endl;
return;
}
int count = 0;
for (int i = 0; i < path.size() - 1; i++)
{
int k1 = mustedge[path[i]];
int k2 = mustedge[path[i + 1]];
if (k1 == k2 && (k1 != -1 && k2 != -1))
{
mustedgesum--;
mustedge[path[i]] = -1;
mustedge[path[i + 1]] = -1;
cout << "(" << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(4) << path[i] << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(4) << path[i + 1] << ")";
count++;
if (count == 5)
{
cout << endl;
count = 0;
}
}
}
cout << "the number of non visited necessary edges " << mustedgesum << endl;
//cout << mustedgesum << endl;
if (mustedgesum>0)cout << "error path" << endl;
return;
}
void startseacher(vector>>&map, vector&Ants, int &maxnodes, vector&mustgo)
{
ofstream fout("result.txt");
vectorbestpath, shortpath(1000, 0);
vectorbestorder, shortorder;
int bestcost = INF, shortcost = INF;
int bestAnt=-1, shortAnt=-1;
int Nc = 0, NcMax = 100;
int len = map.size();
int lastbest = 0;
int lastshort = 0;
int count = 0;// ，
int num = 1;
while (1)
{
cout << "Nc=" << Nc << endl;
if (Nc - lastbest > 5 && Nc - lastshort > 5)
{
count++;
cout << "count=" << count << endl;
if (count < 3&&nodes<50)
{
Init_S(map);
lastbest = Nc;
lastshort = Nc;
}
else
{
break;
}
}
//cout << "lastbest=" << lastbest << " lastshort=" << lastshort << endl;
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < Ants.size(); j++)
{
if (Ants[j].MovedCityCount == len)continue;
vectorpt(len, 0.0);
int curcity = Ants[j].CurCity;
int to = -1;
//cout << "i=" << i << " j=" << j << " curcity=" << curcity << endl;
int k1 = mustedge[mustgo[curcity].value];
int tempk = -1;
for (int k = 0; k < len; k++)
{
//cout << "i=" << i << " j=" << j << " k=" << k << endl;
if (Ants[j].AllowedCity[k] == 1 && k != len - 1&&Ants[j].MovedCityCount< len-1)
{
vectorway = map[curcity][k];
double p = 0.0;
double length = 0.0, cost = 0.0;
int k2 = mustedge[mustgo[k].value];
if (k1 != -1 && k2 != -1 && k2 == k1)
{
pt[k] = INF;
tempk = k;
//cout << "curcity=" << curcity << " k=" << k << endl;
break;
//cout << pt[k] << endl;
//getchar();
}
if (way.size()>0)
{
for (int i0 = 0; i0 < tao[curcity][k].size(); i0++)p = p + tao[curcity][k][i0];
for (int i0 = 0; i0 < way.size(); i0++)
{
length = length + way[i0].waynodes;
cost = cost + way[i0].waycost;
}
length = length*1.0 / way.size();
cost = cost*1.0 / way.size();
length = 0.0*length + 1.0*cost;//
//length = way[0].waynodes*0.0 + way[0].waycost*1.0;
if (length < 1)length = 0.5;// 0；
pt[k] = pow(p, alfa)*pow(1.0 / length, beta);
}
}
if (k == len - 1 && Ants[j].MovedCityCount == len - 1)
{
to = len - 1;
pt[k] = 1000.0;
break;
}
}
while (1)
{
if (tempk != -1)
{
to = tempk;
break;
}
to = choose(pt);
//cout << "to=" << to << endl;
if (Ants[j].AllowedCity[to] == 1 && to != -1)break;
cout << "to=" << to << endl;
if (to == 0)
{
cout << "error" << endl;
getchar();
exit(-1);
}
}
//cout << "i=" << i << " j=" << j << " to=" << to << endl;
Ants[j].Order.push_back(to);
vectorway = map[curcity][to];
//cout << "i=" << i << " j="<=1 && i0 < way[index].way.size()-1)//
{
int temp1 = temp;
int temp2 = way[index].way[i0+1];
int k1 = mustedge[temp1];
int k2 = mustedge[temp2];
//cout << " temp1=" << temp1 << " temp2=" << temp2 << endl;
//cout << " k1=" << k1 << " k2=" << k2 << endl;
if (k1 != -1 && k2 != -1 && k1 == k2)
{
//show(father);
int k3 = father[temp1];
int k4 = father[temp2];
//cout << " k3=" << k3 << " k4=" << k4 << endl;
//if (k3 == 999 || k4 == 999)cout << " k3=" << k3 << " k4=" << k4 << endl;
if (Ants[j].AllowedCity[k3] == 1&&k3!=endnode)//
{
Ants[j].AllowedCity[k3] = 0;
Ants[j].MovedCityCount++;
}
if (Ants[j].AllowedCity[k4] == 1 && k4 != endnode)//
{
Ants[j].AllowedCity[k4] = 0;
Ants[j].MovedCityCount++;
}
}
}
if (i0 >= 1 && i0 < way[index].way.size() - 1)//
{
//cout << "temp=" << temp << endl;
if (ismustnode[temp] != -1)
{
int k1 = father[temp];
//cout << " k1=" << k1 << endl;
//if (k1 == 999)cout << " k1=" << k1 << endl;
if (Ants[j].AllowedCity[k1] == 1&&k1!=endnode)//
{
Ants[j].AllowedCity[k1] = 0;
Ants[j].MovedCityCount++;
}
}
}
if (temp > endnode)//
{
int tempindex = findnodes(virtualnode, temp);
//cout << "tempindex=" << tempindex << endl;
if (tempindex != -1)
{
temp = virtualnode[tempindex].index;
}
}
Ants[j].Path.push_back(temp);
}
Ants[j].Cost = Ants[j].Cost + way[index].waycost;
}
if (Ants[j].AllowedCity[to] == 1)
{
Ants[j].AllowedCity[to] = 0;
Ants[j].MovedCityCount++;
}
//cout << "i=" << i << " j="<=1000)w = 5;
else if (nodes >= 100)w = 4;
else if (nodes>10)w = 3;
else w = 2;
for (int i = 0; i < bestpath.size(); i++)
{
fout << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(w) << bestpath[i];
if ((i + 1) % 20 == 0)fout << endl;
}
fout << endl;
}
if (shortpath.size() < 1000)
{
cout << "shortpath" << endl;
cout << "cost=" << shortcost << endl;
cout << "nodes=" << shortpath.size() << endl;
show(shortpath);
fout << "shortpath" << endl;
fout << "cost=" << shortcost << endl;
fout << "nodes=" << shortpath.size() << endl;
int w = 5;
if (nodes >= 1000)w = 5;
else if (nodes >= 100)w = 4;
else if (nodes>10)w = 3;
else w = 2;
for (int i = 0; i < bestpath.size(); i++)
{
fout << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(w) << bestpath[i];
if ((i + 1) % 20 == 0)fout << endl;
}
fout << endl;
}
else
{
shortpath = bestpath;
shortcost = bestcost;
cout << "There is no way to satisfy the restricted vertex number" << endl;
cout << "The recommended path:" << endl;
cout << "cost=" << shortcost << endl;
cout << "nodes=" << shortpath.size() << endl;
show(shortpath);
fout << "There is no way to satisfy the restricted vertex number" << endl;
fout << "The recommended path:" << endl;
fout << "cost=" << shortcost << endl;
fout << "nodes=" << shortpath.size() << endl;
int w = 5;
if (nodes >= 1000)w = 5;
else if (nodes >= 100)w = 4;
else if (nodes>10)w = 3;
else w = 2;
for (int i = 0; i < bestpath.size(); i++)
{
fout << setiosflags(ios::right) << setiosflags(ios::fixed) << setw(w) << shortpath[i];
if ((i + 1) % 20 == 0)fout << endl;
}
fout << endl;
}
cout << "time=" << (clock() - start)*1.0 / CLOCKS_PER_SEC<>_a(MAXN, vector(MAXN, INF));
edgenum = 0;
a = _a;
memset(first, -1, sizeof(first));
memset(first1, -1, sizeof(first1));
mustedges.clear();
mustnodes.clear();//
notedges.clear();//
virtualnode.clear();
setmustnodeset;
cout << "input your map path, if you input quick, the program will exit" << endl;
cin >> s;
fstream fin(s);
startnode = 0;
if (s == "quick")
{
break;
}
if (!fin.is_open())
{
cout << "your path is error" << endl;
exit(-1);
}
int maxnode;
while (fin >> nodes >> edges>>maxnode)
{
start = clock();
//cout << nodes << " " << edges << " " << maxnode << endl;
endnode = nodes - 1;
vector>v;
for (int i = 0; i < edges; i++)
{
int temp1, temp2, temp3;
fin >> temp1 >> temp2 >> temp3;
//cout << temp1 << " " << temp2 << " " << temp3 << endl;
//vectortemp{ temp1, temp2, temp3, 1 };
a[temp1][temp2] = temp3;
a[temp2][temp1] = temp3;
//v.push_back(temp);
}
int mustgonodes, mustgoedges;
fin >> mustgonodes;
for (int i = 0; i < mustgonodes; i++)
{
int temp;
fin >> temp;
mustnodeset.insert(temp);
}
fin >> mustgoedges;
setsetmustedges;
for (int i = 0; i < mustgoedges; i++)
{
int temp1, temp2;
fin >> temp1 >> temp2;
//cout << temp1 << " " << temp2 << " " << endl;
if (mustnodeset.count(temp1) != 0)mustnodeset.erase(temp1);
if (mustnodeset.count(temp2) != 0)mustnodeset.erase(temp2);
if (setmustedges.count(temp1) == 0 && setmustedges.count(temp2) == 0)
{
vectortemp = { temp1, temp2 };
mustedges.push_back(temp);
setmustedges.insert(temp1);
setmustedges.insert(temp2);
}
else if (setmustedges.count(temp1) == 0 || setmustedges.count(temp2) == 0)
{
if (setmustedges.count(temp1) != 0 && setmustedges.count(temp2) == 0)
{
mustvirtualnode.insert(temp1);
cout << "temp1=" << temp1 << endl;
Node temp = { temp1, nodes };
vectortempv = { nodes, temp2 };
mustedges.push_back(tempv);
virtualnode.push_back(temp);
a[temp1][nodes] = a[temp1][temp2];
a[nodes][temp1] = a[temp1][nodes];
a[nodes][temp2] = 0;
a[temp2][nodes] = 0;
nodes++;
}
if (setmustedges.count(temp2) != 0 && setmustedges.count(temp1) == 0)//temp2
{
mustvirtualnode.insert(temp2);
cout << "temp2=" << temp2 << endl;
Node temp = { temp2, nodes };
vectortempv = { temp1, nodes };
mustedges.push_back(tempv);
virtualnode.push_back(temp);
a[temp2][nodes] = a[temp1][temp2];
a[nodes][temp2] = a[temp2][nodes];
a[nodes][temp1] = 0;
a[temp1][nodes] = 0;
nodes++;
cout << "nodes" << endl;
}
setmustedges.insert(temp2);
setmustedges.insert(temp1);
}
else //
{
a[temp1][nodes] = a[temp1][temp2];
a[nodes][temp1] = a[temp1][temp2];
Node tn = { temp1, nodes };
virtualnode.push_back(tn);
int temp = nodes;
nodes++;
a[temp][nodes] = 0;
a[nodes][temp] = 0;
vectortempv = { temp, nodes };
mustedges.push_back(tempv);
a[nodes][temp2] = 0;
a[temp2][nodes] = 0;
tn = { temp2, nodes };
virtualnode.push_back(tn);
nodes++;
}
}
for (set::iterator p = mustnodeset.begin(); p != mustnodeset.end(); p++)mustnodes.push_back(*p);
for (int i = 0; i < mustedges.size(); i++)
{
//cout << mustedges[i][0] << " " << mustedges[i][1] << endl;
}
int notedgenums;
fin >> notedgenums;
for (int i = 0; i < notedgenums; i++)//
{
int temp1, temp2;
fin >> temp1 >> temp2;
//cout << temp1 << " " << temp2 << " " << endl;
a[temp1][temp2] = INF;
a[temp2][temp1] = INF;
}
v.clear();
for (int i = 0; i < nodes - 1; i++)
{
for (int j = i + 1; j < nodes; j++)
{
if (a[i][j] != INF)
{
//cout << "here" << endl;
add(i, j, a[i][j]);
add(j, i, a[i][j]);
}
}
}
}
int mincost = 0;
vectorbestorder, bestpath;
int newnodes = mustnodes.size() + mustedges.size() * 2 + 2;// ， ，
vectormustgo(mustnodes.size() + mustedges.size() * 2 + 2);
vector>>map(newnodes, vector>(newnodes));
{
Init(map, mustgo);
Ant ant(map.size());
vectorants(map.size()*2/3, map.size());
Init_S(map);
startseacher(map, ants, maxnode, mustgo);
}
fin.close();
}
}