【第十六届北京师范大学程序设计竞赛决赛（网络同步赛）】F汤圆防漏理论（点权和的最小值，vector/set）

【第十六届北京师范大学程序设计竞赛决赛（网络同步赛）】F汤圆防漏理论（点权和的最小值，vector/set）

ghc很喜欢吃汤圆，但是汤圆很容易被粘(zhān)漏。 根据多年吃汤圆经验，ghc总结出了一套汤圆防漏理论： 互相接触的汤圆容易粘(zhān)在一起，并且接触面积不同，粘(zhān)在一起的粘(nián)度也不同。 当ghc要夹起一个汤圆时，这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和，如果大于汤圆的硬度，这个汤圆就会被粘(zhān)漏。 今天ghc又要煮汤圆啦，今天要煮n个汤圆，并且摆盘的方法已经设计好： 汤圆按照1, 2, \dots , n编号，有m对汤圆互相接触，用x_i, y_i, z_i表示编号为x_i和y_i的两个汤圆互相接触，粘(nián)度为z_i。 汤圆当然是越软越好吃，但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么，汤圆的硬度最小可以是多少，可以满足吃的过程中，存在一种夹汤圆的顺序，使得没有汤圆会被粘(zhān)漏呢？ 注意： 不考虑汤圆的重力作用； 不能同时夹多个汤圆； 吃完汤圆一定要喝点汤。 Input 第一行是一个正整数T(\leq 5)，表示测试数据的组数， 对于每组测试数据， 第一行是两个整数n,m(1\leq n,m\leq 100000)， 接下来m行，每行包含三个整数x_i, y_i, z_i(1\leq x_i, y_i \leq n, x_i \neq y_i, 1 \leq z_i \leq 1000000)， 同一对汤圆不会出现两次。 Output 对于每组测试数据，输出一行，包含一个整数，表示汤圆硬度的最小值。 Sample Input 1 4 6 1 2 2 1 3 2 1 4 2 2 3 3 2 4 3 3 4 5 Sample Output 6 Source 第十六届北京师范大学程序设计竞赛决赛 Author zhuaiballl 【vector+结构体】 #include using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) #define memc(a,b) memcpy(a,b,sizeof(b)) #define rep(i,a,n) for(int i=a;im.w; } }; vectorg[N]; bool vis[N]; ll sum[N]; int n,m; void solve() { priority_queuepq; rep(i,1,n+1) pq.push({i,sum[i]}); ll ans=0; while(!pq.empty()) { Node now=pq.top(); pq.pop(); if(vis[now.node]) continue; vis[now.node]=1; ans=max(ans,now.w); for(auto tmp:g[now.node]) { sum[tmp.v]-=tmp.w; pq.push({tmp.v,sum[tmp.v]}); } } printf("%lld\n",ans); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); rep(i,0,n+1) g[i].clear(),vis[i]=0; for(int i=0;i using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) #define memc(a,b) memcpy(a,b,sizeof(b)) #define rep(i,a,n) for(int i=a;iP; set

g[N]; bool vis[N]; ll sum[N]; int n,m; void solve() { priority_queue,greater

>pq; rep(i,1,n+1) pq.push({sum[i],i}); ll ans=0; while(!pq.empty()) { P now=pq.top(); pq.pop(); ll u=now.second; ll w=now.first; if(sum[u]!=now.first) continue; ans=max(ans,w); for(set

::iterator it=g[u].begin();it!=g[u].end();it++) { ll v=it->second; ll nw=it->first; g[v].erase(P(nw,u)); sum[v]-=nw; pq.push(P(sum[v],v)); } } printf("%lld\n",ans); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); rep(i,0,n+1) g[i].clear(),sum[i]=0; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。