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

网站建设开发案例网站建设制作流程

网站建设开发案例,网站建设制作流程,医疗网站建设策划,网站做专题换根DP 一般是给定一棵不定根树,求以每个节点为根的一些信息。可以通过二次扫描: 第一次扫描,任选一点为根,在有根树上,自底向上转移第二次扫描,从上一次扫描的根开始,自顶向下计算 P3478 [P…

换根DP

一般是给定一棵不定根树,求以每个节点为根的一些信息。可以通过二次扫描:

  • 第一次扫描,任选一点为根,在有根树上,自底向上转移
  • 第二次扫描,从上一次扫描的根开始,自顶向下计算

P3478 [POI2008] STA-Station

题意:

询问以哪个节点为根,所有节点的深度和最大。深度为到根节点的距离。

解析:

第一次扫描:以节点1为根(任意一个节点都可以),求出深度和。

第二次扫描:设第一次扫描时 v v v u u u 的儿子。假设根节点由 u u u 变为 v v v v v v 子树内所有节点的深度-1,不在 v v v 子树内的所有节点深度+1。 f v = f u − s i z e v + n − s i z e v f_v= f_u-size_v+n-size_v fv=fusizev+nsizev n n n 为所有节点数。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct edge{int to, nxt;
}e[maxn << 1];
int head[maxn], siz[maxn], tot, dep[maxn];
void add(int a, int b){e[++tot].nxt = head[a];e[tot].to = b;head[a] = tot;
}
int n, m;
ll f[maxn];
void dfs(int u, int fa){siz[u] = 1;dep[u] = dep[fa] + 1;for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;dfs(v, u);siz[u] += siz[v];}
}
void dfs2(int u, int fa){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;f[v] = f[u] + n - siz[v] * 2;dfs2(v, u);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i < n; i++){int u, v;cin >> u >> v;add(u, v); add(v, u);}dfs(1, 0);for(int i = 1; i <= n; i++)f[1] += dep[i];dfs2(1, 0);ll maxx = -1, res;for(int i = 1; i <= n; i++){if(maxx < f[i]){res = i;maxx = f[i];}}cout << res << endl;return 0;
}


P2986 [USACO10MAR] Great Cow Gathering G

题意:

一棵树,边有边权,点有点权。询问以哪个点为根时, ∑ i = 1 n d i s ( i , r o o t ) ⋅ a i \sum\limits_{i=1}\limits^ndis(i, root) \cdot a_i i=1ndis(i,root)ai a i a_i ai 为点权, d i s ( i , r o o t ) dis(i,root) dis(i,root) 为节点 i i i 与根节点的距离。

解析:

第一次扫描:
以1节点为根, f u f_u fu 表示 u u u 子树内节点到 u u u 距离点权的乘积的和。设 v v v u u u 的儿子,则 f u = ∑ ( f v + s i z e v × e ( u , v ) ) f_u =\sum(f_v+size_v\times e(u,v)) fu=(fv+sizev×e(u,v)) e ( u , v ) e(u,v) e(u,v) ( u , v ) (u,v) (u,v) 边的长度。

第二次扫描:
设第一次扫描时 v v v u u u 的儿子。假设根节点由 u u u 变为 v v v v v v 子树内所有节点到根节点的距离减小 e ( u , v ) e(u,v) e(u,v),不在 v v v 子树内的所有节点到根节点的距离增加 e ( u , v ) e(u,v) e(u,v) f v = f u + ( n − 2 × s i z e v ) × e ( u , v ) f_v= f_u+(n-2\times size_v)\times e(u,v) fv=fu+(n2×sizev)×e(u,v) n n n 为所有节点数。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;#define int ll
struct edge{int to, nxt, w;
}e[maxn << 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){e[++tot].nxt = head[a];e[tot].to = b;e[tot].w = c;head[a] = tot;
}
int n, m;
ll f[maxn], a[maxn], sum;
void dfs(int u, int fa){siz[u] = a[u];for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;dfs(v, u);siz[u] += siz[v];f[u] += f[v] + siz[v] * e[i].w;}
}
void dfs2(int u, int fa){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;f[v] = f[u] - siz[v] * e[i].w + (sum - siz[v]) * e[i].w;dfs2(v, u);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}for(int i = 1; i < n; i++){int u, v, w;cin >> u >> v >> w;add(u, v, w); add(v, u, w);}dfs(1, 0);dfs2(1, 0);ll res = INF;for(int i = 1; i <= n; i++)res = min(res, f[i]);cout << res << endl;return 0;
}


积蓄程度

题意:

一棵树,根节点可以流出无限水,叶子节点可以吸收无限水,每条边有流量限制。询问以哪个点为根节点时,叶子节点吸收的水最多。

解析:

第一次扫描:

f u f_u fu 为以1为根节点时,以 u u u 为根的子树中,吸收的水量。

v v v u u u 的儿子:
{ f u + = m i n ( f v , w ( u , v ) ) , d e g v = 1 f u + = w ( u , v ) , d e g v ≠ 1 \begin{cases} f_u += min(f_v, w(u, v)), & deg_v = 1\\ f_u += w(u, v), & deg_v \neq 1 \end{cases} {fu+=min(fv,w(u,v)),fu+=w(u,v),degv=1degv=1

第二次扫描:

g u g_u gu 为以 u u u 为根节点时,最大流量。

设第一次扫描时 v v v u u u 的儿子。假设根节点由 u u u 变为 v v v

g v g_v gv 包括两部分:

  • 一部分是第一次扫描的 f v f_v fv
  • 一部分是流向 u u u 进而流向其他节点

u u u 而言,从 u u u v v v 的流量为 m i n ( f j , w ( i , j ) ) min(f_j, w(i,j)) min(fj,w(i,j)),流向 v v v 之外的流量为 g u − m i n ( f j , w ( i , j ) ) g_u - min(f_j, w(i,j)) gumin(fj,w(i,j))。所以 g v g_v gv 的第二部分为 m i n ( w ( u , v ) , g u − m i n ( f j , w ( i , j ) ) ) min(w(u,v), g_u - min(f_j, w(i,j))) min(w(u,v),gumin(fj,w(i,j)))。也需要按照度是否为1讨论一下: { g v = f v + w ( u , v ) d e g u = 1 g v = f v + m i n ( g u − w ( u , v ) , w ( u , v ) ) d e g u ≠ 1 , d e g v = 1 g v = f v + m i n ( g u − m i n ( f v , w ( u , v ) ) , w ( u , v ) ) , d e g u ≠ 1 , d e g v ≠ 1 \begin{cases} g_v = f_v+ w(u, v) & deg_u = 1\\ g_v = f_v + min(g_u-w(u,v), w(u, v)) &deg_u \neq 1 ,deg_v = 1\\ g_v = f_v + min(g_u-min(f_v, w(u,v)), w(u,v)),& deg_u \neq 1 ,deg_v \neq 1 \end{cases} gv=fv+w(u,v)gv=fv+min(guw(u,v),w(u,v))gv=fv+min(gumin(fv,w(u,v)),w(u,v)),degu=1degu=1,degv=1degu=1,degv=1

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;#define int ll
struct edge{int to, nxt, w;
}e[maxn << 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){e[++tot].nxt = head[a];e[tot].to = b;e[tot].w = c;head[a] = tot;
}
int n, m;
ll f[maxn], g[maxn], deg[maxn];
void dfs(int u, int fa){f[u] = 0;for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;dfs(v, u);if(deg[v] == 1)f[u] += e[i].w;elsef[u] += min(e[i].w, f[v]);}
}
void dfs2(int u, int fa){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;if(deg[u] == 1)g[v] = f[v] + e[i].w;else if(deg[v] == 1)g[v] = f[v] + min(g[u]-e[i].w, e[i].w);elseg[v] = f[v] + min(g[u]-min(f[v], e[i].w), e[i].w);dfs2(v, u);}
}
void solve(){cin >> n;memset(deg, 0, sizeof(deg));tot = 0;memset(head, 0, sizeof(head));for(int i = 1; i < n; i++){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);deg[a]++; deg[b]++;}dfs(1, 0);g[1] = f[1];dfs2(1, 0);ll res = 0;for(int i = 1; i <= n; i++)res = max(res, g[i]);cout << res << endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T;cin >> T;while(T--)solve();return 0;
}
http://www.15wanjia.com/news/18139.html

相关文章:

  • 收银系统哪个软件好重庆百度seo公司
  • 胶南网南昌seo营销
  • 网站首页背景图片阐述网络营销策略的内容
  • 手机建站模版广州四楚seo顾问
  • 外贸官网建站做网站建设公司
  • 都安做网站湖北网站seo设计
  • php网站开发编程软件来客seo
  • 网站建设的原理电商怎么做新手入门
  • 湖州市城乡建设局网站网络营销与直播电商好就业吗
  • 自己做网站需要什么软件下载seo是指什么岗位
  • 网站备案完了怎么做百度竞价什么意思
  • 什么网站可以做网站友情链接可以随便找链接加吗
  • php mysql网站开发全程实例.pdf中超最新积分榜
  • 做宣传图片用什么网站必应搜索引擎下载
  • 专门做微信推送的网站论坛优化seo
  • 重庆高端网站seowhois查询
  • 泉州免费建站查指数
  • 网站首页怎么做营销型网站模板
  • 网站 东莞长安企业宣传推广方案
  • 网站站内搜索代码长春建站程序
  • 域名注册 网站建设 好做吗torrent种子搜索引擎
  • 潍坊网站建设首荐创美网络世界网站排名查询
  • 搜索引擎手机动态网站制作设计百度灰色关键词排名
  • 沧州市做网站价格怎么做网上销售
  • 网站友情链接是什么天津seo数据监控
  • 网站建设技个人如何优化网站有哪些方法
  • 公司主营业务网站建设德阳seo优化
  • 一个网站有哪些优势贵阳网站建设公司
  • 晾衣架 东莞网站建设企业seo推广
  • 网站什么时候做负载均衡推广自己的网站