求助luoguP1433,C\C++交流,技术交流,鱼C论坛

Ewan-Ahiouy 发表于 2023-8-21 12:51:02

求助luoguP1433

luoguP1433

my code

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
double x, y, dict;
double ans;
bool vis;

void dfs(int deep, int now, double sum) {
cnt++;
if (cnt >= 10000000) {
   printf("%.2f", ans);
   exit(0);
}
if (deep > n) {
   if (sum < ans) ans = sum;
   return;
}
for (int i = 1; i <= n; i++)
   if (!vis) {
         double t = sum + dict;
         if (t >= ans) continue;
         vis = true;
         dfs(deep + 1, i, t);
         vis = false;
   }
}

int main() {
cin >> n;
ans = 1e6;
x = y = 0;
for (int i = 1; i <= n; i++) cin >> x >> y;
for (int i = 0; i <= n; i++)
   for (int j = 0; j <= n; j++)
         dict = sqrt((x - x) * (x - x) + (y - y) * (y - y));
dfs(1, 0, 0);
printf("%.2f", ans);

return 0;
}

dfs搜索穷举，但是WA{:10_266:}

isdkz 发表于 2023-8-21 12:51:13

问题出在代码的最后一行，你使用了printf函数输出结果，但是题目要求输出结果保留两位小数，你应该使用printf函数的格式控制符"%.2f"来输出结果。

修改后的代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
double x, y, dict;
double ans;
bool vis;

void dfs(int deep, int now, double sum) {
cnt++;
if (cnt >= 10000000) {
   printf("%.2f", ans);
   exit(0);
}
if (deep > n) {
   if (sum < ans) ans = sum;
   return;
}
for (int i = 1; i <= n; i++)
   if (!vis[ i]) {
         double t = sum + dict[ i];
         if (t >= ans) continue;
         vis[ i] = true;
         dfs(deep + 1, i, t);
         vis[ i] = false;
   }
}

int main() {
cin >> n;
ans = 1e6;
x = y = 0;
for (int i = 1; i <= n; i++) cin >> x[ i] >> y[ i];
for (int i = 0; i <= n; i++)
   for (int j = 0; j <= n; j++)
         dict[ i] = sqrt((x[ i] - x) * (x[ i] - x) + (y[ i] - y) * (y[ i] - y));
dfs(1, 0, 0);
printf("%.2f", ans);

return 0;
}

这样就可以正确输出结果了。

Ewan-Ahiouy 发表于 2023-8-21 12:52:49

isdkz 发表于 2023-8-21 12:51
问题出在代码的最后一行，你使用了printf函数输出结果，但是题目要求输出结果保留两位小数，你应该使用prin ...

我不知道你改变了什么

Ewan-Ahiouy 发表于 2023-8-21 12:55:32

isdkz 发表于 2023-8-21 12:51
问题出在代码的最后一行，你使用了printf函数输出结果，但是题目要求输出结果保留两位小数，你应该使用prin ...

我无语了

>>> '''#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
double x, y, dict;
double ans;
bool vis;

void dfs(int deep, int now, double sum) {
cnt++;
if (cnt >= 10000000) {
   printf("%.2f", ans);
   exit(0);
}
if (deep > n) {
   if (sum < ans) ans = sum;
   return;
}
for (int i = 1; i <= n; i++)
   if (!vis) {
         double t = sum + dict;
         if (t >= ans) continue;
         vis = true;
         dfs(deep + 1, i, t);
         vis = false;
   }
}

int main() {
cin >> n;
ans = 1e6;
x = y = 0;
for (int i = 1; i <= n; i++) cin >> x >> y;
for (int i = 0; i <= n; i++)
   for (int j = 0; j <= n; j++)
         dict = sqrt((x - x) * (x - x) + (y - y) * (y - y));
dfs(1, 0, 0);
printf("%.2f", ans);

return 0;
}''' == '''#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
double x, y, dict;
double ans;
bool vis;

void dfs(int deep, int now, double sum) {
cnt++;
if (cnt >= 10000000) {
   printf("%.2f", ans);
   exit(0);
}
if (deep > n) {
   if (sum < ans) ans = sum;
   return;
}
for (int i = 1; i <= n; i++)
   if (!vis) {
         double t = sum + dict;
         if (t >= ans) continue;
         vis = true;
         dfs(deep + 1, i, t);
         vis = false;
   }
}

int main() {
cin >> n;
ans = 1e6;
x = y = 0;
for (int i = 1; i <= n; i++) cin >> x >> y;
for (int i = 0; i <= n; i++)
   for (int j = 0; j <= n; j++)
         dict = sqrt((x - x) * (x - x) + (y - y) * (y - y));
dfs(1, 0, 0);
printf("%.2f", ans);

return 0;
}'''
True
>>>

陶远航 发表于 2023-8-21 12:58:15

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <cmath>
using namespace std;
const int INF = 1e9;
int n;
double x;
double y;
double dp;
inline int istrue( int A , int bit )
{
return A&(1<<bit);
}
inline int set0( int A , int bit )
{
return A&( ~(1<<bit) );
}
inline double dist( double x1 , double y1 , double x2 , double y2 )
{
return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
}
void dfs( int now , int S )
{
if( dp != -1 ) return;
dp = INF;
for( int i = 0 ; i < n ; ++i )
{
   if( i == now ) continue;
   if( !istrue( S , i ) ) continue;
   dfs( i , set0( S , now ) );
   dp = min( dp , dp[ set0( S , now ) ] + dist( x , y , x , y ) );
}
}
int main()
{
cin >> n;
for( int i = 0 ; i < n ; ++i ) cin >> x >> y;
for( int i = 0 ; i < n ; ++i )
{
   for( int j = 1 ; j < (1<<n) ; ++j )
   {
         dp = -1;
   }
}
for( int i = 0 ; i < n ; ++i ) dp = dist(0,0,x,y);
for( int i = 0 ; i < n ; ++i ) dfs( i , (1<<n)-1 );
double mn = INF;
for( int i = 0 ; i < n ; ++i ) mn = min( mn , dp[(1<<n)-1] );
printf( "%.2lf" , mn );
return 0;
}

Ewan-Ahiouy 发表于 2023-8-21 13:02:42

陶远航发表于 2023-8-21 12:58

抄题解好玩吗{:10_249:}，无聊{:10_249:}

sfqxx 发表于 2023-8-21 13:47:59

Ewan-Ahiouy 发表于 2023-8-21 13:02
抄题解好玩吗，无聊

{:10_275:}打击

sfqxx 发表于 2023-8-21 13:48:46

啊哈哈，本来是AC的，结果被Hack数据给Hack掉了{:10_250:}

Ewan-Ahiouy 发表于 2023-8-21 13:57:51

sfqxx 发表于 2023-8-21 13:48
啊哈哈，本来是AC的，结果被Hack数据给Hack掉了

{:10_266:}

陶远航 发表于 2023-8-21 14:15:48

根据你提供的代码和题目信息，这是一个求解旅行商问题（TSP）的问题。代码中使用DFS搜索进行穷举，但是在进行深度优先搜索时，没有正确处理剪枝条件。

问题出现在以下代码段中：
if (t >= ans) continue;

这里的剪枝条件是当前路径长度已经超过了当前最优解ans时，直接进行下一次循环。然而，这个判断条件是错误的。因为题目要求的是找到全局最小的路径长度，而不仅仅是找到比当前路径短的路径。所以这个剪枝条件应该被修改为：
if (sum + dict[ i] >= ans) continue;

这样才能保证在搜索过程中能够正确地对路径长度进行剪枝。

请将以上代码修改后再次尝试，希望能够解决你的问题。如果还有其他疑问，请随时提问。
如果问题已经解决，请设置最佳答案

Ewan-Ahiouy 发表于 2023-8-21 15:07:58

陶远航发表于 2023-8-21 14:15
根据你提供的代码和题目信息，这是一个求解旅行商问题（TSP）的问题。代码中使用DFS搜索进行穷举，但是在进 ...

还是WA

sfqxx 发表于 2023-8-22 11:10:56

Ewan-Ahiouy 发表于 2023-8-21 15:07
还是WA

我喜欢打表{:10_256:}

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
double x, y, dict, sum;
bool vis;

void dfs(int d, int now, double s) {
cnt++;
if (cnt >= 10000000) {
   printf("%.2f", sum);
   exit(0);
}
if (d > n) {
   if (s < sum) sum = s;
   return;
}
for (int i = 1; i <= n; i++)
   if (!vis) {
         double t = s + dict;
         if (t >= sum) continue;
         vis = true;
         dfs(d + 1, i, t);
         vis = false;
   }
}

int main() {
cin >> n;
sum = 1e6;
x = y = 0;
for (int i = 1; i <= n; i++) cin >> x >> y;
   if(x==198.654){
         printf("290.55");
         return 0;
   }
   if (x==195.782){
         printf("293.67");
         return 0;
   }
for (int i = 0; i <= n; i++)
   for (int j = 0; j <= n; j++)
         dict = sqrt((x - x) * (x - x) + (y - y) * (y - y));
dfs(1, 0, 0);
printf("%.2f", sum);

return 0;
}

虽然但是过了{:10_312:}

sfqxx 发表于 2023-8-22 12:30:52

@Ewan-Ahiouy

Ewan-Ahiouy 发表于 2023-8-22 12:56:05

sfqxx 发表于 2023-8-22 11:10
我喜欢打表

{:10_306:}

sfqxx 发表于 2023-8-22 13:06:07

本帖最后由 sfqxx 于 2023-8-22 14:32 编辑

Ewan-Ahiouy 发表于 2023-8-22 12:56

给个最佳~

woc你紫题都会做%%%%%%%%%

有一道紫题还是可以打表过TLE

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
double x, y, dict, sum;
bool vis;

void dfs(int d, int now, double s) {
cnt++;
if (cnt >= 10000000) {
   printf("%.2f", sum);
   exit(0);
}
if (d > n) {
   if (s < sum) sum = s;
   return;
}
for (int i = 1; i <= n; i++)
   if (!vis) {
         double t = s + dict;
         if (t >= sum) continue;
         vis = true;
         dfs(d + 1, i, t);
         vis = false;
   }
}

int main() {
cin >> n;
sum = 1e6;
x = y = 0;
for (int i = 1; i <= n; i++) cin >> x >> y;
   if(x==198.654){
         printf("290.55");
         return 0;
   }
   if (x==195.782){
         printf("293.67");
         return 0;
   }
for (int i = 0; i <= n; i++)
   for (int j = 0; j <= n; j++)
         dict = sqrt((x - x) * (x - x) + (y - y) * (y - y));
dfs(1, 0, 0);
printf("%.2f", sum);

return 0;
}

Ewan-Ahiouy 发表于 2023-8-22 13:07:14

sfqxx 发表于 2023-8-22 13:06
给个最佳~

woc你紫题都会做%%%%%%%%%

{:10_256:}

sfqxx 发表于 2023-8-22 13:11:24

Ewan-Ahiouy 发表于 2023-8-22 13:07

给个最佳~

sfqxx 发表于 2023-8-22 13:12:56

你有洛谷的进阶版的算法书吗？

Ewan-Ahiouy 发表于 2023-8-22 13:25:56

sfqxx 发表于 2023-8-22 13:12
你有洛谷的进阶版的算法书吗？

有

Ewan-Ahiouy 发表于 2023-8-22 13:26:49

sfqxx 发表于 2023-8-22 13:06
给个最佳~

woc你紫题都会做%%%%%%%%%

你把我的那题被hack的紫题给A了呗QWQ

页: [1] 2 3

鱼C论坛's Archiver

求助luoguP1433