首页 > 其他分享 >Solution - Codeforces 1394B Boboniu Walks on Graph

Solution - Codeforces 1394B Boboniu Walks on Graph

时间:2024-11-12 21:46:10浏览次数:1  
标签:二元 int Graph ll 入度 Solution Codeforces maxn rk

考虑先分析最后的图会长成什么样。
因为每个点都只会连出一条有向边,且最后还能走回自己。
所以可以知道的是图会有许多个环来组成,且每个环都无交。

但是这个判定条件明显不是很优秀,考虑继续转化。
考虑到对于一个有向环,每个点的出度和入度都需要为 \(1\)。
那么出度为 \(1\) 题目本身就要求满足了,所以实际上只需要使得每个点的入度都为 \(1\) 就可以了。

那么继续转化,考虑反面,那就是要求不存在点的入度 \(> 1\)。
(为什么不考虑入度 \(= 0\) 的?因为边数总共为 \(n\),有入度为 \(0\) 就一定有入度 \(> 1\) 的。)

那么就比较好做了,处理出一个点 \(v\) 对应的入边 \((u, v, w)\) 在 \(u\) 处对应的出边的排名和 \(u\) 的入度,表示为二元组 \((\operatorname{rk_{u, v, w}, deg_u})\)。
那么对于两条入边 \((u, v, w)\) 和 \((u', v, w)\),就要求这两条边对应的二元组 \((rk_{u, v, w}, deg_u), (rk_{u', v, w'}, deg_{u'})\) 不能同时被选中。

那么因为总共的二元组个数不超过 \(1 + 2 + \cdots + 9 = 45\) 个,可以直接二进制压缩。
用 \(f_u\) 表示选了 \(u\) 就不能选的二元组的集合,可以通过每一个点 \(v\) 的情况推出。

那么就可以直接爆搜,每次选出一个出度对应的二元组后判断是否会产生冲突即可。

时间复杂度 \(\mathcal{O}(nk\log k + k!)\)。

#include<bits/stdc++.h>
using ll = long long;
constexpr int maxn = 2e5 + 10;
constexpr int pre[10] = {0, 0, 1, 3, 6, 10, 15, 21, 28, 36};
inline int id(int x, int y) {
   return x + pre[y];
}
int n, m, k;
std::vector<std::pair<int, int> > to[maxn];
int c[maxn][45];
ll f[maxn], g[45];
int ans;
void dfs(int d, ll mask) {
   if (d > k) {
      return ans++, void();
   }
   for (int i = 0; i < d; i++) {
      if (g[id(i, d)] & (mask | (1ll << id(i, d)))) continue;
      dfs(d + 1, mask | (1ll << id(i, d)));
   }
}
int main() {
   scanf("%d%d%d", &n, &m, &k);
   for (int x, y, z; m--; ) {
      scanf("%d%d%d", &x, &y, &z);
      to[x].emplace_back(z, y);
   }
   for (int i = 1; i <= n; i++) {
      std::sort(to[i].begin(), to[i].end());
      for (int j = 0; j < to[i].size(); j++) {
         int v = to[i][j].second, w = id(j, to[i].size());
         c[v][w]++;
         f[v] |= 1ll << w;
      }
   }
   for (int i = 1; i <= n; i++) {
      for (int w = 0; w < 45; w++) {
         if (f[i] >> w & 1ll) {
            g[w] |= f[i] ^ ((ll)(c[i][w] == 1) << w);
         }
      }
   }
   dfs(1, 0);
   printf("%d\n", ans);
   return 0;
}

标签:二元,int,Graph,ll,入度,Solution,Codeforces,maxn,rk
From: https://www.cnblogs.com/rizynvu/p/18542696

相关文章

  • Solution - Codeforces 1217E Sum Queries?
    对于这个“好的”的判定条件看起来有点奇怪,不妨结合上题目要求的“最小\(sum\)”一起考虑。因为要最小化\(s_p\),所以一个比较直观的想法是先从选的数个数入手。考虑到如果选的只有\(1\)个数\(a_i\),那么\(sum=a_i\),一定是好的,排除。如果选的是\(2\)个数\(a_i,a_j\),......
  • LangGraph高级特性:总结与注意事项
    LangGraph作为一个强大的图结构程序设计工具,提供了许多高级特性来支持复杂的AI应用开发。本文将深入探讨LangGraph的一些关键概念和注意事项,帮助开发者更好地利用这个工具。1.数据状态与归纳函数在LangGraph中,理解数据状态的处理方式至关重要。默认情况下,节点返回的字典数据会......
  • LangGraph的两种基础流式响应技巧
    在构建复杂的AI应用时,LangGraph作为一个强大的工具,为我们提供了灵活的图结构程序设计能力。今天,我们将深入探讨LangGraph中的一个关键特性:流式响应模式。这个特性不仅能提高应用的响应速度,还能为用户提供更加流畅的交互体验。LangGraph中的流式响应:与传统LLM有何不同?在LangGraph......
  • 大数据Flink - StreamGraph
    ⭐简单说两句⭐✨正在努力的小新~......
  • 密码学之MD5(Cryptography MD5)
      ......
  • Educational Codeforces Round 80 (CF1288)
    EducationalCodeforcesRound80(CF1288)A.Deadline题意给出正整数\(n,d\),求不等式\(x+\lceil\frac{d}{x+1}\rceil\len\)是否有非负整数解。思路先不考虑上取整,\[x+\frac{d}{x+1}=x+1+\frac{d}{x+1}-1\ge2\sqrtd-1\]当且仅当\(x+1=\frac{d}{x+1}\)即\(......
  • [题解](更新中)Refact.ai Match 1 (Codeforces Round 985)
    A-Set显然答案是\(\max(\lfloor\frac{r}{k}\rfloor-l+1,0)\)。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intt,l,r,k;signedmain(){ cin>>t; while(t--){ cin>>l>>r>>k; cout<<max(0ll,......
  • Educational Codeforces Round 158 (Rated for Div. 2) - VP记录
    A.LineTrip油量必须支持车子通过所有加油站间的空间,还要注意开回来的时候终点不能加油。点击查看代码#include<cstdio>#include<algorithm>usingnamespacestd;constintN=55;intn,x,a[N];intmain(){ intT;scanf("%d",&T); while(T--) { scanf("%d%d",&am......
  • LangGraph中的检查点与人机交互
    一、LangGraph的检查点机制检查点机制是LangGraph中一个强大的功能,它允许我们在图执行的特定点暂停处理,保存状态,并在需要时恢复。1.1检查点的基本概念检查点本质上是图执行过程中的一个快照,包含了当前的状态信息。这对于长时间运行的任务、需要人工干预的流程,或者需要断点续传......
  • 使用LangGraph构建复杂AI工作流:子图架构详解
    一、子图架构概述子图(Subgraph)是LangGraph中一个强大的特性,它允许我们将复杂的工作流程分解成更小、更易管理的组件。通过子图,我们可以实现模块化设计,提高代码的可重用性和可维护性。1.1子图的基本概念子图本质上是一个完整的图结构,可以作为更大图结构中的一个节点使用。它具......