网站建设公司的运营方式,高端网站建设1,婚纱摄影网站论文,大数据技术与应用题干#xff1a;
Rinne 最近了解了如何快速维护可支持插入边删除边的图#xff0c;并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图#xff0c;每条边有一个边权 wiwi
现在她想玩一个游戏#xff1a;选取一个 “重要点” S#xff0c;然…题干
Rinne 最近了解了如何快速维护可支持插入边删除边的图并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图每条边有一个边权 wiwi
现在她想玩一个游戏选取一个 “重要点” S然后选择性删除一些边使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权现在 Rinne 想知道完成这个游戏的最小的代价这样她就能轻松到达 rk1 了作为回报她会让你的排名上升一定的数量。 输入描述:
第一行三个整数 N,M,S意义如「题目描述」所述。接下来 M 行每行三个整数 u,v,w 代表点 u 到点 v 之间有一条长度为 w 的无向边。
输出描述:
一个整数表示答案。
示例1
输入
复制
4 3 1
1 2 1
1 3 1
1 4 1输出
复制
3
说明
需要使得点 2,3,4 不能到达点 1显然只能删除所有的边答案为 3
示例2
输入
复制
4 3 1
1 2 3
2 3 1
3 4 2输出
复制
1
说明
需要使得点 4 不能到达点 1显然删除边 2↔32↔3是最优的。
备注:
2≤S≤N≤105,MN−12≤S≤N≤105,MN−1保证答案在 C long long 范围内。
解题报告 不算难的树形dp刚开始读题错了所以代码不太对、、 于是题目转变求为了一棵根为 S 的树选择性切掉一些边使得所有的叶子都不能到达根的最小代价。 让我们考虑树形dp其实可能就是个统计算不上dp设 fv 表示使得以 v 为根的子树内的叶子到不了 v 的最小代价转移显然枚举每一条边切不切就可以了。 方程大概是这样设当前我们要更新的点是 uu 的一个儿子是 v他们之间的边的边权是 w。则有转移方程 fumin{fv,w}。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includectime
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int t;
int n,m,s,tot;
int head[MAX];
int in[MAX];
struct Edge{int u,v,ne;ll w;
} e[MAX];
void add(int u,int v,ll w) {e[tot].u u;e[tot].v v;e[tot].w w;e[tot].ne head[u];head[u] tot;
}
ll dfs(int cur,int root,ll val) {//ll res 9223372036854775807;ll tmp 0;for(int i head[cur]; i!-1; ie[i].ne) {if(e[i].v root) continue;//res min(res,e[i].w);if(in[e[i].v] 1) {tmp e[i].w;continue;}
// if(in[e[i].v] 1) continue;tmp dfs(e[i].v,cur,e[i].w);}return min(tmp,val);
}
int main()
{cinnms;memset(head,-1,sizeof head);int a,b;ll c;for(int i 1; im; i) {scanf(%d%d%lld,a,b,c);add(a,b,c);add(b,a,c);in[a],in[b];}ll ans 0;for(int i head[s]; i ! -1; i e[i].ne) {if(in[e[i].v] 1) ans e[i].w;else ans dfs(e[i].v,s,e[i].w); } printf(%lld\n,ans);return 0 ;
}错误代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includectime
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int t;
int n,m,s,tot;
int head[MAX];
int in[MAX];
struct Edge{int u,v,ne;ll w;
} e[MAX];
void add(int u,int v,ll w) {e[tot].u u;e[tot].v v;e[tot].w w;e[tot].ne head[u];head[u] tot;
}
ll dfs(int cur,int root) {ll res 9223372036854775807;//int isye 1;for(int i head[cur]; i!-1; ie[i].ne) {if(e[i].v root) continue;//isye 0;res min(res,e[i].w);if(in[e[i].v] 1) {continue;}res min(res,dfs(e[i].v,cur));}//if(isye 1) returnreturn res;
}
int main()
{cinnms;memset(head,-1,sizeof head);int a,b;ll c;for(int i 1; im; i) {scanf(%d%d%lld,a,b,c);add(a,b,c);add(b,a,c);in[a],in[b];}ll ans 0;for(int i head[s]; i ! -1; i e[i].ne) {if(in[e[i].v] 1) ans e[i].w;else ans dfs(e[i].v,s);}printf(%lld\n,ans);return 0 ;
}
AC代码2
#includebits/stdc.h
using namespace std;
int n,m,s;
struct edge
{int to;int cost;
};
vectoredge e[110005];
bool vis[100005];
int mem[100005];
long long dp(int i,int pre)
{if(e[i].size()1i!s){return e[i][0].cost;}if(mem[i]!-1)return mem[i];vis[i]1;long long res0;int nxt;int co;edge tmp;for(int j0;je[i].size();j){tmpe[i][j];nxttmp.to;if(vis[nxt])continue;cotmp.cost;resdp(nxt,min(co,pre));}resmin(res,(long long)pre);mem[i]res;return res;
}
int main()
{//freopen(in.txt,r,stdin);memset(mem,-1,sizeof(mem));scanf(%d%d%d,n,m,s);int u,v,w;edge tmp;for(int i1;im;i){scanf(%d%d%d,u,v,w);tmp.costw;tmp.tov;e[u].push_back(tmp);tmp.tou;e[v].push_back(tmp);}long long ansdp(s,0x3f3f3f3f);coutansendl;return 0;
}官方标程
#include algorithm
#include iostream
#include cstring
#include climits
#include cstdio
#include vector
#include cstdlib
#include ctime
#include cmath
#include queue
#include stack
#include map
#include set#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i a;i b;i)
#define ROF(i,a,b) for(Re int i a;i b;--i)
#define SFOR(i,a,b,c) for(Re int i a;i b;ic)
#define SROF(i,a,b,c) for(Re int i a;i b;i-c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf(--------------------\n)
#define DEBUG(x) std::cerr #x x std::endlconst int MAXN 1000005;struct Edge{int to,w,next;
}e[MAXN1];
int head[MAXN],cnt;
LL f[MAXN];inline void add(int u,int v,int w){e[cnt] (Edge){v,w,head[u]};head[u] cnt;
}void dfs(int v,int fa0){bool flag true;for(int i head[v];i;i e[i].next){if(e[i].to fa) continue;flag false;dfs(e[i].to,v);f[v] std::min(1ll*e[i].w,f[e[i].to]);}if(flag) f[v] INT_MAX;
}int N,root;int main(){scanf(%d%*d%d,N,root);FOR(i,1,N-1){int u,v,w;scanf(%d%d%d,u,v,w);add(u,v,w);add(v,u,w);}dfs(root);printf(%lld\n,f[root]);return 0;
}
