Olá, estou tentando fazer um programa para o problema do caixeiro comprador exato (TPP ou PCCo) e, depois de fazer algumas pesquisas, eu encontrei o código a baixo e gostaria conseguir compilar e executar para comparar com a minha implementação. O problema é que não consigo compilar o código. Fica dando, esses erros(Também segue na foto):
"
/tmp/ccvk9cDb.o: Na função "work()":
main.cpp:(.text+0x104e): relocação truncada para caber: R_X86_64_PC32 contra símbolo não definido "pop" na seção .bss em /tmp/ccvk9cDb.o
main.cpp:(.text+0x106e): relocação truncada para caber: R_X86_64_PC32 contra símbolo não definido "pop" na seção .bss em /tmp/ccvk9cDb.o
main.cpp:(.text+0x1152): relocação truncada para caber: R_X86_64_PC32 contra símbolo não definido "pop" na seção .bss em /tmp/ccvk9cDb.o
main.cpp:(.text+0x12b4): relocação truncada para caber: R_X86_64_PC32 contra símbolo não definido "pop" na seção .bss em /tmp/ccvk9cDb.o
/tmp/ccvk9cDb.o: Na função "__static_initialization_and_destruction_0(int, int)":
main.cpp:(.text+0x1526): relocação truncada para caber: R_X86_64_PC32 contra ".bss"
main.cpp:(.text+0x1539): relocação truncada para caber: R_X86_64_PC32 contra ".bss"
collect2: error: ld returned 1 exit status
"
Esse é o código:
//////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <bitset>
#include"instance_access.h"
#define INF 0x3f3f3f3f
#define eps 1e-8
#define FI first
#define SE second
using namespace std;
typedef long long ll;
const int MaxM = 25, MaxK = 700;
int M, K, Q;
int G[MaxM + 5][MaxM + 5];
int P[MaxM + 5][MaxK + 5];
int C[MaxM + 5];
void read(char *p,int m,int k,int d,int h)
{
//scanf("%d%d", &M, &K);
int* _graph;
int* _price;
//_graph->printMatrix();
//cout<<endl;
//_price->printMatrix();
//cout<<endl;
get_instance_largek(_graph,_price,m,k,p);
//cout<<endl;
for(int i=0;i<m;++i)
{
for(int j=0;j<m;++j)
{
int temp=_graph[i*m+j];
//cout<<temp<<" ";
*(G + j)=temp;
}
//cout<<endl;
}
//cout<<endl;
for(int i=0;i<m;++i)
{
for(int j=0;j<k;++j)
{
int temp=_price[i*k+j];
// cout<<temp<<" ";
*(P + j)=temp;
}
// cout<<endl;
}
M=m;
K=k;
Q=h;
for(int i=1;i<m;++i)
{
C=d;
}
}
inline void ck(int &x, int v) {
if(x > v) x = v;
}
int head[MaxM + MaxK + 10];
struct Edge {
int nxt, to, cow, cost;
Edge() {}
Edge(int nxt, int to, int cow, int cost) : nxt(nxt), to(to), cow(cow), cost(cost) {}
} ed[100000];
int ecnt, mx_flow, mi_cost;
void init() {
mx_flow = mi_cost = ecnt = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cow, int cost) {
ed[ecnt] = Edge(head, v, cow, cost);
head = ecnt ++;
ed[ecnt] = Edge(head[v], u, 0, -cost);
head[v] = ecnt ++;
}
queue <int> q;
int dis[MaxK + MaxM + 10], pre[MaxK + MaxM + 10], inq[MaxK + MaxM + 10];
bool Spfa(int S, int T) {
memset(dis, 0x3f, sizeof(dis));
dis = 0;
q.push(S);
while(!q.empty()) {
int u = q.front(); q.pop();
inq = 0;
for(int e = head; ~e; e = ed[e].nxt) {
if(!ed[e].cow) continue;
int v = ed[e].to;
if(dis[v] > dis + ed[e].cost) {
dis[v] = dis + ed[e].cost;
pre[v] = e;
if(!inq[v]) {
inq[v] = 1;
q.push(v);
}
}
}
}
return dis[T] != INF;
}
void End(int S, int T) {
int flow = INF;
for(int u = T; u != S; u = ed[pre ^ 1].to) {
flow = min(flow, ed[pre].cow);
}
for(int u = T; u != S; u = ed[pre ^ 1].to) {
ed[pre].cow -= flow;
ed[pre ^ 1].cow += flow;
mi_cost += flow * ed[pre].cost;
}
mx_flow += flow;
}
int minPrice(int s) {
init();
int src = 0, dec = M + K+1;
for(int i = 1; i < M; ++ i) {
if(~s >> i & 1) continue;
addedge(src, i, C, 0);
for(int k = 0; k < K; ++ k) {
if(P[k] == 0) continue;
addedge(i, M + k+1, 1, P[k]);
}
}
for(int i = 1; i <= K; ++ i) {
addedge(M + i, dec, 1, 0);
}
while(Spfa(src, dec)) End(src, dec);
if(mx_flow != K) return -1;
return mi_cost;
}
int dp[MaxM + 1][1 << MaxM];
int pop[1 << MaxM];
void work() {
int U = 1 << M;
for(int i = 1; i < U; ++ i) {
pop = pop[i >> 1] + (i & 1);
}
for(int i = 1; i < M; ++ i) {
for(int j = 0; j < U; ++ j) {
dp[j] = INF;
}
}
for(int i = 1; i < M; ++ i) {
dp[1 << i] = G[0];
}
for(int s = 1; s < U; ++ s) {
if(pop >= Q) continue;
for(int i = 1; i < M; ++ i) {
if(dp == INF) continue;
for(int j = 1; j < M; ++ j) {
if(s >> j & 1) continue;
ck(dp[j][s | (1 << j)], dp + G[j]);
}
}
}
int ans = INF;
for(int i = 0; i < U; ++ i) {
if(pop > Q) continue;
int f = minPrice(i);
if(f == -1) continue;
for(int j = 1; j < M; ++ j) {
if(dp[j] == INF) continue;
ck(ans, f + dp[j] + G[j][0]);
}
}
printf("%d", ans);
}
int main(int argc,char *argv[]) {
//arguments order: filename m k u q
if(argc !=6)
{
cout<<"wrong number of arguments";
return 1;
}
int m,k,u,q;
m=atoi(argv[2]);
k=atoi(argv[3]);
u=atoi(argv[4]);
q=atoi(argv[5]);
read(argv[1],m,k,u,q);
time_t begin,end;
cout<<"optimal object value: ";
begin=clock();
work();
end=clock();
cout<<endl;
cout<<"time: ";
cout<<double(end-begin)/CLOCKS_PER_SEC<<endl;
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////"instance_acess.h"//////////////////////////////////////////////////////////
#ifndef INSTANCE_ACCESS_H_INCLUDED
#define INSTANCE_ACCESS_H_INCLUDED
#include <string>
#include <strstream>
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
int get_instance_largek(int *&graph, int *&product_distribution, int m,int k,char *p)
{
graph=new int[m*m];
product_distribution=new int[m*k];
for(int i=0;i<m;++i)
{
for(int j=0;j<m;++j)
{
graph[i*m+j]=0;
}
}
for(int i=0;i<m;++i)
{
for(int j=0;j<k;++j)
{
product_distribution[i*k+j]=0;
}
}
ifstream fin;
fin.open(p);
if(fin.is_open())
{
string s;
while(fin>>s)
{
if(s=="NODE_COORD_SECTION")
{
fin>>s;
int num;
double x[m];
double y[m];
for(int i=0;i<m;++i)
{
fin>>num;
fin>>x;
fin>>y;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
double xd=x-x[j];
double yd=y-y[j];
int d=(int)(sqrt(xd*xd+yd*yd)+0.5);
graph[i*m+j]=d;
}
}
}
if(s=="OFFER_SECTION")
{
fin>>s;
int id;
int num=0;
for(int i=0;i<m;++i)
{
fin>>id;
fin>>num;
int product_id;
int cost;
int dem;
for(int j=0;j<num;++j)
{
fin>>product_id;
fin>>cost;
product_distribution[i*k+product_id-1]=cost;
fin>>dem;
}
}
}
}
return 1;
}else{
return 0;
}
}
#endif // INSTANCE_ACCESS_H_INCLUDED
//////////////////////////////////////////////////////////////////////////////////////////////