CF1301F - Super Jaber

发表于 | 阅读数

$𝑛≤80$个点完全有向连通图，走𝑘步回到起点1且没有奇环，求最小代价

没有奇环，考虑染色。所以我们可以把图染色成一个二分图，在二分图上跑dp就行。一定就是偶数环。

选中的概率是$(\frac{1}{2})^{10}$,多跑几次就好了。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <ctime>
using namespace std;
typedef long long ll;
const int N = 100;
const int mod = 1e9 + 7;
int dp[N][N], d[N][N];
int n, c[N], m;
int main()
{
    srand(time(0));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &d[i][j]);
    int T = 512 * 20, ans = 1e9;
    while (T--)
    {
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 1; i <= n; i++)
            c[i] = rand() & 1;
        dp[1][0] = 0;
        for (int t = 1; t <= m; t++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (c[i] != c[j])
                        dp[i][t] = min(dp[i][t], dp[j][t - 1] + d[j][i]);
        ans = min(ans, dp[1][m]);
    }
    printf("%d\n", ans);
}