首先，我想引用一个“初等路径”的定义。点此查看 简而言之，对于这个问题，我们需要找到一条k-元路径S，使得到w1的权重最小，所有边的和到w2小于或等于Q，并且它确切地有K个边。Given an undirected graph G = (V, E) with two parameter of weights w1 and w2 for each edges. This graph has N vertices and M edges. A K-Elementary path S is a sub-graph of G which must be an elementary graph and it does have exactly K edges.
Find a K-elementary path S with the sum of w1 of all edges as minimum value and the sum of w2 of all edges of S must be smaller than a given value Q. If it does not exist any path satisfied, print out the value -1
Input:
The first line with four values N, M, K, Q (2 <= N, K <= 50, 1 <= M <= 2*N, 1 <= Q <= 10^9)
The next M lines show the edges of the graph: V1 V2 W1 W2 (1 <= V1, V2 <= N, 1 <= W1 <= 10^4, 1 <= W2 <= 10^4)
Output: One integer to show the minimum weight of the k-elementary graph found. -1 if non-exists
Sample test case:
Input:
5 7 3 6 1 2 1 2 1 4 2 2 1 5 3 6 2 3 3 2 2 4 4 4 3 4 5 1 4 5 4 7Output:
6
我有一种回溯法的方法，尝试构建满足第二个条件（w2）的所有图形，然后找到第一个条件（w1）的最小值，但是，正如您所知，时间复杂度很高。然而，我发现很难将其转换为动态规划或任何其他方法来降低时间复杂度。我已经添加了一些分支限界条件，但仍然很慢。
以下是我的源代码，您可以参考，但我认为它没有用。
#include <bits/stdc++.h>
using namespace std;
#define N 51
#define INF 1e9
int n, m, K, Q;
bool appear[N];
int W1[N][N];
int W2[N][N];
int currentSum1 = 0;
int currentSum2 = 0;
int source = 0;
int res = INF;
int Log[N];
int minElement = INF;
bool check(int k, int v)
{
return !appear[v] && W1[Log[k - 1]][v] != 0 && W2[Log[k - 1]][v] != 0;
}
void solution()
{
if(currentSum1 != 0 && currentSum1 < res)
{
res = currentSum1;
// for(int i = 0; i <= K; i++)
// cout << Log[i] << " ";
// cout << endl;
}
}
void solve(int k)
{
for(int v = 1; v <= n; v++)
{
if(check(k, v) && currentSum2 + W2[source][v] <= Q && currentSum1 + (K - k) * minElement <= res) //Branch-bound condition
{
Log[k] = v;
currentSum2 += W2[Log[k - 1]][v];
currentSum1 += W1[Log[k - 1]][v];
appear[v] = true;
if(k == K)
solution();
else
solve(k + 1);
currentSum1 -= W1[Log[k - 1]][v];
currentSum2 -= W2[Log[k - 1]][v];
appear[v] = false;
}
}
}
int main()
{
fast;
// freopen("data.txt", "r", stdin);
cin >> n >> m >> K >> Q;
for(int i = 0; i < m; i++)
{
int x, y, w1, w2;
cin >> x >> y >> w1 >> w2;
minElement = min(minElement, w1);
W1[x][y] = w1;
W1[y][x] = w1;
W2[x][y] = w2;
W2[y][x] = w2;
}
for(int v = 1; v <= n; v++)
{
source = v;
currentSum2 = 0;
currentSum1 = 0;
Log[0] = v;
for(int i = 1; i <= n; i++)
appear[i] = false;
appear[source] = true;
solve(1);
}
if(res != INF)
cout << res << endl;
else
cout << -1 << endl;
}