2020-2021:teams:legal_string:jxm2001:图论_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:图论_1 [2020/07/26 12:51] jxm2001 |
2020-2021:teams:legal_string:jxm2001:图论_1 [2020/08/01 00:05] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 850: | 行 850: | ||
| * 任意两个双连通分量间无公共点和公共边 | * 任意两个双连通分量间无公共点和公共边 | ||
| - | 求边-双连通分量有两种方法，与求点-双连通分量类似。 | + | 求边-双连通分量有两种方法，与求点-双连通分量类似。一般考虑先一次 $\text{dfs}$ 求出桥，再一次 $\text{dfs}$ 染色，染色过程中不经过桥。 |
| - | === 例题 === | + | 使用上述方法求边-双连通分量时需要注意标记桥时需要将双向边同时标记，如果只标记了双向边的某一条边，染色过程中可能出现错误。 |
| + | |||
| + | === 例题 1 === | ||
| [[https://www.luogu.com.cn/problem/P3225|洛谷p3225]] | [[https://www.luogu.com.cn/problem/P3225|洛谷p3225]] | ||
| 行 970: | 行 972: | ||
| printf("Case %d: %d %llu\n",++kase,ans1,ans2); | printf("Case %d: %d %llu\n",++kase,ans1,ans2); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | |||
| + | === 例题 2 === | ||
| + | |||
| + | [[https://codeforces.com/contest/1389/problem/G|edu 92 G题]] | ||
| + | |||
| + | == 题意 == | ||
| + | |||
| + | 给定 $n$ 个点 $m$ 条边的无向图，其中 $k$ 个点为特殊点，每个点有一个点权，每条边有一个边权。 | ||
| + | |||
| + | 要求给无向图的边定向，如果将某条边定向为单向边，则不需要支付费用。如果将某条边定向为双向边，则需要支付等于该边边权的费用。 | ||
| + | |||
| + | 定义图中的某个点为满足当且仅当所有特殊点可以到达沿有向边到达该点，且如果某个边成为满点，则可以获得等于该点点权的利润。 | ||
| + | |||
| + | 要求输出 $n$ 个数，表示如果第 $i$ 个点为满点能得到的最大收益，其中收益 $=$ 利润 $-$ 费用。 | ||
| + | |||
| + | == 题解 == | ||
| + | |||
| + | 有结论：对边双连通分量，存在某种策略可以将无向边全部定向为单向边并可以得到强连通分量。 | ||
| + | |||
| + | 于是求出所有边双连通分量并缩点，得到一棵无根树，树上的边为原图的桥，接下来考虑树形 $\text{dp}$。 | ||
| + | |||
| + | 先考虑如何求出第 $1$ 个节点为满点时的最大收益。(这里及下文的节点均指缩点后的节点) | ||
| + | |||
| + | 令第 $1$ 个节点为根节点，设 $\text{dp}(u)$ 为在第 $1$ 个节点为满点且为根节点的前提下 $u$ 是满点时 $u$ 所在子树利益的最大值。 | ||
| + | |||
| + | 首先 $\text{dp}(u)$ 的初值为 $u$ 缩点中所有点的点权和。接下来考虑状态转移，假设节点 $u$ 为满点，考虑它的子节点 $v$。 | ||
| + | |||
| + | 如果所有特殊点都在子节点 $v$ 的子树中，则 $v$ 一定是满点且连一条 $v\to u$ 的单向边，于是 $\text{dp}(u)\gets \text{dp}(v)$。 | ||
| + | |||
| + | 如果所有特殊点都不在子节点 $v$ 的子树中，则贪心连一条 $u\to v$ 的单向边一定最优，于是 $\text{dp}(u)\gets \text{dp}(v)$。 | ||
| + | |||
| + | 除了上面两种特殊情况，则由于子节点 $v$ 的子树中存在特殊节点，且 $u$ 为满点，所以必须能从 $v$ 走到 $u$。 | ||
| + | |||
| + | 于是要么 $v$ 连一条单向边到 $u$，这样 $v$ 不是满点，对 $u$ 无贡献。要么 $v,u$ 间连一条双向边，于是贡献为 $dp(v)-w(u,v)$。 | ||
| + | |||
| + | 所以该情况下有状态转移方程 $dp(u)=\max(0,dp(v)-w(u,v))$。 | ||
| + | |||
| + | 根据上述方法，可以 $O(n)$ 求解第 $1$ 个节点为满点时的最大收益，接下来考虑换根 $\text{dp}$。 | ||
| + | |||
| + | 不断转移根，假设当前根为 $u$，$v$ 为 $u$ 的子节点。 | ||
| + | |||
| + | 于是先减去 $v$ 对 $u$ 的贡献，这样树被分成了以 $u$ 为根节点的树和以 $v$ 为根节点的树这两棵树。 | ||
| + | |||
| + | 然后考虑将 $u$ 节点转化为 $v$ 的子节点并计算贡献。 | ||
| + | |||
| + | 换根采用 $\text{dfs}$ 过程且需要回溯。总时间复杂度 $O(n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e5+5; | ||
| + | struct Edge{ | ||
| + | int from,to,id,next; | ||
| + | }edge[MAXN<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v,int idx){ | ||
| + | edge[++edge_cnt]=Edge{u,v,idx,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_sp[MAXN],bcc_cnt; | ||
| + | bool is_bridge[MAXN]; | ||
| + | LL bcc_v[MAXN],dp[MAXN],ans[MAXN]; | ||
| + | vector<int> bcc[MAXN]; | ||
| + | vector<pair<int,int> >g[MAXN]; | ||
| + | int k,c[MAXN],node_sp[MAXN],edge_w[MAXN]; | ||
| + | void dfs(int u,int fa){ | ||
| + | low[u]=dfs_id[u]=++dfs_t; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==fa)continue; | ||
| + | if(!dfs_id[v]){ | ||
| + | dfs(v,u); | ||
| + | low[u]=min(low[u],low[v]); | ||
| + | if(low[v]>dfs_id[u]) | ||
| + | is_bridge[edge[i].id]=true; | ||
| + | } | ||
| + | else | ||
| + | low[u]=min(low[u],dfs_id[v]); | ||
| + | } | ||
| + | } | ||
| + | void dfs_2(int u,int fa){ | ||
| + | bcc_id[u]=bcc_cnt; | ||
| + | bcc_v[bcc_cnt]+=c[u]; | ||
| + | bcc_sp[bcc_cnt]+=node_sp[u]; | ||
| + | bcc[bcc_cnt].push_back(u); | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | if(is_bridge[edge[i].id])continue; | ||
| + | int v=edge[i].to; | ||
| + | if(v==fa||bcc_id[v])continue; | ||
| + | dfs_2(v,u); | ||
| + | } | ||
| + | } | ||
| + | void get_bcc(int n){ | ||
| + | dfs(1,1); | ||
| + | _rep(i,1,n){ | ||
| + | if(!bcc_id[i]){ | ||
| + | bcc_cnt++; | ||
| + | dfs_2(i,i); | ||
| + | } | ||
| + | } | ||
| + | _rep(i,1,edge_cnt){ | ||
| + | if(is_bridge[edge[i].id]){ | ||
| + | int u=bcc_id[edge[i].from],v=bcc_id[edge[i].to]; | ||
| + | g[u].push_back(make_pair(v,edge_w[edge[i].id])); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void update_edge(int u,int v,int d,int w){ | ||
| + | LL t=dp[v]; | ||
| + | if(bcc_sp[v]>0&&bcc_sp[v]<k) | ||
| + | t=max(0LL,dp[v]-w); | ||
| + | dp[u]+=d*t; | ||
| + | bcc_sp[u]+=d*bcc_sp[v]; | ||
| + | } | ||
| + | void dp_1(int u,int fa){ | ||
| + | dp[u]=bcc_v[u]; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i].first,w=g[u][i].second; | ||
| + | if(v==fa)continue; | ||
| + | dp_1(v,u); | ||
| + | update_edge(u,v,1,w); | ||
| + | } | ||
| + | } | ||
| + | void dp_2(int u,int fa){ | ||
| + | ans[u]=dp[u]; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i].first,w=g[u][i].second; | ||
| + | if(v==fa)continue; | ||
| + | update_edge(u,v,-1,w); | ||
| + | update_edge(v,u,1,w); | ||
| + | dp_2(v,u); | ||
| + | update_edge(v,u,-1,w); | ||
| + | update_edge(u,v,1,w); | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n,m,u,v; | ||
| + | n=read_int(),m=read_int(),k=read_int(); | ||
| + | _rep(i,1,k) | ||
| + | node_sp[read_int()]=1; | ||
| + | _rep(i,1,n) | ||
| + | c[i]=read_int(); | ||
| + | _rep(i,1,m) | ||
| + | edge_w[i]=read_int(); | ||
| + | _rep(i,1,m){ | ||
| + | u=read_int(),v=read_int(); | ||
| + | Insert(u,v,i);Insert(v,u,i); | ||
| + | } | ||
| + | get_bcc(n); | ||
| + | dp_1(1,1); | ||
| + | dp_2(1,1); | ||
| + | _rep(i,1,n) | ||
| + | space(ans[bcc_id[i]]); | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/jxm2001/图论_1.1595739086.txt.gz · 最后更改: 2020/07/26 12:51 由 jxm2001
