题解：CF177F1 Script Generation

· · 题解

觉得楼下的题解讲得不太详细，所以写了此篇题解！

题目翻译

翻译

解题思路

应该非常好理解，就是一道关于图的模拟题（也可以理解成链表），可以用结构体模拟。

  1. next：代表一个结点的下一个结点。
  2. head：头结点。
  3. ver：代表一个结点的上一个结点。
  4. edge：代表边权。

题目大概思路是用二分查找第 k 幸福值，但所有值都查找一遍会喜提 TLE，所以一定要用二分。二分中查找的每个值 mid 都要深度优先搜索。

为了让时间复杂度卡在 2 秒之内，需要在 DFS 中剪枝。

前置小知识

二分模板：

int l = 1, r = 10000000, mid;
while (l < r) {
    mid = (l + r) / 2 // 或者mid=(l+r)>>1
        if (check(mid)) l
        = mid; // check函数自由发挥
    else r = mid;
}

链式前向星法模（mú）板：

void add_edge(int x, int y, int z)
{
    a[++tot].next = a[x].head, a[tot].ver = y, a[tot].edge = z;
    a[x].head = tot;
}

接下来我们来看一下代码

#include <bits/stdc++.h>
using namespace std;
int n, k, t;
struct Node {
    int head, next, ver, edge;
} a[1005];
int tot = 0;
bool vis[105];
void add_edge(int x, int y, int z)
{
    a[++tot].next = a[x].head, a[tot].ver = y, a[tot].edge = z;
    a[x].head = tot;
}
int dfs(int x, int sum, int limits)
{
    if (sum > limits)
        return false;
    if (x == n + 1)
        return true;
    int ans = dfs(x + 1, sum, limits);
    for (int i = a[x].head; i; i = a[i].next) {
        int summ = a[i].ver, z = a[i].edge;
        if (ans >= t)
            continue;
        if (vis[i])
            continue;
        vis[summ] = true;
        ans += dfs(x + 1, sum + z, limits);
        vis[summ] = false;
    }
    return ans;
}
bool check(int x)
{
    return dfs(1, 0, x) >= t;
}
int main()
{
    cin >> n >> k >> t;
    for (int i = 1; i <= k; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        y += n;
        add_edge(x, y, z);
    }
    int l = 0, r = 2e5;
    int ans = -114514;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}