当前位置: 首页 > news >正文

学做宝宝衣服网站汕头网站建设技术外包

学做宝宝衣服网站,汕头网站建设技术外包,分销电商,营销型网站建设开发价格更好的阅读体验 Skiers Description 给定 n n n 个点的有向无环平面图,求最少多少条从 1 1 1 到 n n n 的路径能覆盖原图的所有边? 1 ≤ n ≤ 5 1 0 3 1\le n\le 5\times10^3 1≤n≤5103 Solution 考虑从 1 1 1 到 n n n 的路径其实是边的链覆…

更好的阅读体验

Skiers

Description

给定 n n n 个点的有向无环平面图,求最少多少条从 1 1 1 n n n 的路径能覆盖原图的所有边?

1 ≤ n ≤ 5 × 1 0 3 1\le n\le 5\times10^3 1n5×103

Solution

考虑从 1 1 1 n n n 的路径其实是边的链覆盖,那么最小链覆盖即为求解的答案。通过 Dilworth 定理可知,最小链覆盖等于最大反链,从而问题转化为求最大反链(两两无法到达的边的集合)。

例如:图示的有向无环平面图, 1 1 1 号点为起点, 7 7 7 号点为汇点。最大反链是 3 , 4 , 5 , 8 3,4,5,8 3,4,5,8 边构成的集合(注意集合不唯一),不难发现原图的答案就是 4 4 4

考虑如何求解最大反链,可以将平面图转化为对偶图,则最大反链即为对偶图的最长路。

如图,给出了原图的对偶图的最长路,注意这里多开了虚拟起点和汇点。

那么,怎么求最长路呢,这里给出一种简单又迅速的做法,从起点开始 DFS,如果遍历到 1 1 1 个点之前已经遍历过了,那么说明多出了一条对偶图的边。

若绿色路径为当前 DFS 的路径,红色为之前 DFS 的路径,此时发现到达了一个已经经过的点,则从该点开始将红色的边筛出来,直到绿色节点经过过的点,即 1 1 1 号节点。用红色边最长路 + 1 +1 +1 再去更新绿色边的最长路即可。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 5e3 + 10, M = 3 * N;int n;
int h[N], e[M], ne[M], idx;
int st[N], dp[M];
PII lst[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], dp[idx] = 1, h[a] = idx ++;
}
void dfs(int u) {st[u] = 1;for (int i = h[u]; ~i; i = ne[i]) {int v = e[i];if (st[v] == 0) lst[v] = {u, i}, dfs(v);else {int res = 0, tmp = u;while (st[v] == -1) res = max(res, dp[lst[v].se] + 1), v = lst[v].fi;dp[i] = res;while (tmp != v) dp[lst[tmp].se] = res, tmp = lst[tmp].fi;lst[e[i]] = {u, i};}}st[u] = -1;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n;memset(h, -1, sizeof h);int k, x;for (int i = 1; i < n; i ++) {cin >> k;for (int j = 1; j <= k; j ++)cin >> x, add(i, x);}dfs(1);int res = 0;for (int i = 0; i < idx; i ++)res = max(res, dp[i]);cout << res << endl;return 0;
}
http://www.yidumall.com/news/73874.html

相关文章:

  • 厦门网站建设开发百度直播平台
  • 网站维护员招聘怎么制作网页
  • 好的做外贸的网站广州各区风险区域最新动态
  • 如何在网站发广告公司网页制作教程
  • 网站建设费用的会计种子搜索神器 bt 下载
  • 阿里云模板建站好不好厦门seo优化推广
  • 现在网站还用asp做关键词搜索工具好站网
  • 国内php开发的电商网站有哪些小升初最好的补课机构排行榜
  • app手机程序开发百度seo是啥
  • jf厂高仿手表网站苏州新闻今天最新消息新闻事件
  • 制作网站技术东莞seo网站排名优化
  • 海珠区建设和水务局网站优化网站推广教程排名
  • 英文企业网站开发网络营销的主要方式和技巧
  • 唐山seo网络推广百度seo推广怎么收费
  • 商标设计网站主要提供哪些服务企业qq一年多少费用
  • 个人公众号做电影网站吗长沙seo培训班
  • 潍坊网站seo外包网站超级外链
  • 男女直接做那个视频网站腾讯广告代理商加盟
  • 网站开发维护成本计算网站建设公司是怎么找客户
  • 网站建设 psd站内推广的方法和工具
  • 建设银行网站显示404网站seo百度百科
  • 淘宝建设网站首页网站运营需要多少钱
  • 便宜网站制作公司百度经验发布平台
  • 做网站怎样安全采集seo推广主要做什么的
  • 武汉云优化网站建设营销型网站方案
  • 自己创业做网站产品推广软文300字
  • 淘宝网站c#设计怎么做seo自动优化软件安卓
  • 建e全景app优化推广网站排名
  • 怎么做简单的企业网站全网关键词云在哪里看
  • 做网站要准备百度收录规则