#4637. 樱符「完全墨染的樱花」

news/2024/4/21 1:38:19/

题目描述

暂无

数据范围

暂无

题解

考虑到这张图是仙人掌,即一条边最多属于一个简单环。

要求两点间的最大流,即求最小割,那要割的要么是桥边,要么是两条环边。

考虑到如果删去的是环边的话,那一定会删掉边权最小的边。

所以可以把每个环的最小的边删去,同时其他边加上这条边的权值,这样两点间的最小割不会改变,进而只要求一棵树的两点间的最小割即可。

所以用并查集维护即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5,P=998244353;
int n,m,p,t,hd[N],V[N],nx[N],W[N],f[N];
int a[N],b[N],fa[N],d[N],g[N],Q,ans,G;
bool vis[N];struct E{int u,v,w;}e[N],q[N];
bool cmp(E A,E B){return A.w>B.w;}
int get(int x){return f[x]==x?x:f[x]=get(f[x]);
}
int X(int x){return x>=P?x-P:x;}
int K(int x,int y){int z=1;for (;y;y>>=1,x=1ll*x*x%P)if (y&1) z=1ll*z*x%P;return z;
}
void add(int u,int v,int i){nx[++t]=hd[u];V[hd[u]=t]=v;W[t]=i;
}
void dfs(int u,int fr){d[u]=d[fa[u]=fr]+1;for (int i=hd[u];i;i=nx[i])if (V[i]!=fr) g[V[i]]=W[i],dfs(V[i],u);
}
int main(){cin>>n>>m>>p;for (int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);sort(e+1,e+m+1,cmp);for (int i=1;i<=n;i++) f[i]=i;for (int u,v,i=1;i<=m;i++){u=get(e[i].u);v=get(e[i].v);if (u==v) q[++Q]=e[i];else add(e[i].u,e[i].v,i),add(e[i].v,e[i].u,i),f[v]=u;}dfs(1,0);for (int u,v,i=1;i<=Q;i++){u=q[i].u;v=q[i].v;if (d[u]<d[v]) swap(u,v);while(d[u]>d[v]) e[g[u]].w+=q[i].w,u=fa[u];while(u!=v)e[g[u]].w+=q[i].w,u=fa[u],e[g[v]].w+=q[i].w,v=fa[v];}sort(e+1,e+m+1,cmp);for (int i=1;i<=n;i++)f[i]=i,a[i]=K(p,i),b[i]=K(p,1ll*(i-1)*n%(P-1));for (int u,v,i=1;i<=m;i++){u=get(e[i].u);v=get(e[i].v);if (u==v) continue;ans=X(ans+1ll*(1ll*a[u]*b[v]%P+1ll*a[v]*b[u]%P)*e[i].w%P);a[u]=X(a[u]+a[v]);b[u]=X(b[u]+b[v]);f[v]=u;}printf("%d\n",ans);return 0;
}

http://www.ppmy.cn/news/669071.html

相关文章

墨魂服务器维修,#墨魂[超话]# #墨魂一周年# 【... - @墨魂独立工作室 的微博精选 - 微博国际站...

#墨魂[超话]# #墨魂一周年# 【《墨魂》一周年活动细则介绍之叁】 自博山炉重燃、墨痕斋重启&#xff0c;转眼已满一年。在此周年之际&#xff0c;《墨魂》将推出为期三周的庆典&#xff0c;全新活动与墨魂、剧情内容&#xff0c;将陆续与兰台见面。 今日特为兰台介绍周年活动第…

墨汁...

题目描述 小T擅长国画&#xff0c;特别崇拜以画马著称的国画大师徐悲鸿先生&#xff0c;所以小T也很喜欢画马&#xff0c;众所周知画马是需要很多墨汁的&#xff0c;为了节省支出&#xff0c;小T决定参加龙城近墨堂最近推出的以瓶换墨活动&#xff0c;本次活动为期三月&#x…

シグレ / 时雨

目录 基本资料面板值&#xff08;无天冥加成&#xff09;天冥奖励 战斗宣言&#xff08;VC&#xff09;被动效果技能本体AS 珠子 回到人物索引 基本资料 NS(4★)NS(5★)AS卡池 (Ver 2.0.0)卡池 (Ver 2.0.0)卡池 (Ver 2.7.60)—ワタツミの書&#xff08;ミグランス城VH&#x…

西藏,赴一场心灵之约

夏墨 69个想法 ◆ 版权信息 唯有心绪安宁&#xff0c;才能听见灵魂的歌声 ◆ 序言 真正的耳聪目明&#xff0c;是听见心声透视心灵。 城市的喧嚣、生活的沉重、无尽的烦恼闭塞了我们心灵的视听。所以&#xff0c;许多人开始寻求一种救赎&#xff0c;渴望回归澄净。 “那一年&a…

夏末秋初

夏末秋初 &#xff08;作者&#xff0f;形象&#xff09;    我首先要说明的是&#xff1a;这是一个真实的故事。这句话本身就有矛盾&#xff0c;既然是故事&#xff0c;又何谓真实呢&#xff1f;但终究是真实&#xff0c;至少对于故事而言。   真实这东西&#xff0c;几乎…

墨韵

自己在Boostrap的基础上进行自己原创的一个国学响应式网站&#xff0c;个人觉得总体看起来还是比较大气&#xff0c;古香古色的。 用到了轮播图&#xff0c;图片堆叠布局旋转木马效果。 先来看一下效果图&#xff0c;有哪些地方不足的&#xff0c;请各位大神多指教 1.首页的…

《墨舞》

突然意识到很久没有和弟弟一起默契的哼唱同一首喜欢的歌&#xff0c;好久没有因为喜欢同一个东西而争吵;很久没有和他玩最爱玩的电子游戏&#xff0c;好久没有因为游戏只能一个人玩而打架.只是因为我们都不再是那个什么都不用操心的孩子了&#xff0c;我们都长大了&#xff0c;…

他曾经来过—墨茶

周五的时候看到一位up主因无钱治疗去世&#xff0c;看到的时候就感觉心口一震&#xff0c;眼眶顿然就湿了&#xff0c;为什么人生这么苦&#xff1f;打工&#xff0c;黑心老板&#xff0c;父母抛弃&#xff0c;高中辍学&#xff0c;病魔这样的字眼萦绕在脑海里&#xff0c;这样…

アィシャ / 艾夏

目录 基本资料面板值&#xff08;无天冥加成&#xff09;天冥奖励 战斗宣言&#xff08;VC&#xff09;被动效果技能 回到人物索引 基本资料 NS(5★)角色任务1入队 (Ver 2.13.81) 天冥属性武器防具属性耐性异常耐性NS天火&水杖戒指火&风30%10%个性杖、吟游诗人、诅咒…

夏弥

“我最讨厌那些胸围大的女生了&#xff01;”夏弥异常严肃&#xff0c;一秒钟后她换了沮丧的脸&#xff0c;歪着脑袋&#xff0c;“她们欺负人&#xff01;” 夏弥捂脸&#xff0c;“我还说学长你带我来六旗游乐园第一站就是摩天轮果然浪漫得非同一般&#xff0c;还以为你因为…

【Python 随练】将一个数组逆序输出

题目&#xff1a; 将一个数组逆序输出 简介&#xff1a; 在本篇博客中&#xff0c;我们将解决一个数组操作问题&#xff1a;将一个数组逆序输出。我们将介绍数组逆序的概念&#xff0c;并提供一个完整的代码示例来实现逆序输出数组。 问题分析&#xff1a; 我们需要将给定…

GDB 断点管理

1、b 设置断点 usage 1: b 函数名 usage 2: b 文件名:行号 2、rb 函数名关键字 &#xff1a; 所有带有这个关键字的函数名都设置为断点 (gdb) rb dkauth Breakpoint 7 at 0x34187ae0: file /home/jintao/cvf/apps/cvf/services/dkauth/src/dkauth.c, line 58. void dkauth_…

C++ DAY4

1.思维导图 2.运算符重载 #include <iostream> using namespace std;class Person { private:int age;int *p; public://1.无参构造Person():p(new int(89)){age 18;}//2.有参构造Person(int age,int num){this->age age;this->pnew int(num);}//3.拷贝构造函数…

【ArcGIS微课1000例】0069:用ArcGIS提取一条线的高程值

本实验讲解用ArcGIS软件,基于数字高程模型DEM提取一条线的高程值并导出。 文章目录 一、加载实验数据二、将线转为折点三、提取折点高程值四、导出高程值五、注意事项【相关阅读】:【GlobalMapper精品教程】060:用dem提取一条线的高程值 一、加载实验数据 本实验使用的数据…

2022年12月份青少年软件编程Python等级考试试卷六级真题(含答案)

一、单选题(共25题&#xff0c;共50分) 1.数据文件“abc.txt”中包含若干个英文单词&#xff0c;如图所示&#xff1a; 读取文件“abc.txt”中数据的Python程序段如下&#xff1a; file abc.txt word_b [] for word in open(file):if word[0:1] a and len(word)>4:wo…

[创业之路-74] - 感悟 - 创业是所有因素的机缘组合,缺一不可; 舰船思维 VS 城堡思维.

感悟: 方向、趋势、路径、资助、船只、船长、大副、水手、船员、装备、配套、路径…… 一个都不能少 只看对方向与趋势&#xff0c;一样葬身在趋势的洪流中 看不对方向与趋势&#xff0c;亦会老死在寂寞孤冷之中 在所有因素中&#xff1a; 船只、装配、配套是最表象和最容易…

python和pyqt5编写的软件为何闪退

本人解释&#xff0c;这个标题纯属噱头&#xff0c;为了赚一点点击率&#xff0c;其实应该叫&#xff0c;《用python的catch捕获无关紧要的异常》。 废话不多说&#xff0c;上实际情况。 def open(self):strFilter"document file(*.docx);;text file(*.txt)"fileName…

Orcad软件闪退问题解决

orcad因为一次异常关闭后&#xff0c;再次启动软件时始终闪退&#xff0c;无法正常打开。在百度上找到的方法都是千篇一律的&#xff0c;按照这些方法软件反复重装破解清注册表了好多回&#xff0c;问题依然如故。 后来回想起在安装软件时有提示要确认一个home目录&#xff0c…

Win10解决自带查看照片软件的闪退问题

Win10解决自带查看照片软件的闪退问题 文章目录 Win10解决自带查看照片软件的闪退问题 今天在公司里面遇到同事想要进行照片的大小调整&#xff0c;然后在自己的电脑上点开照片发现照片一直是闪退&#xff0c;经过自己查看资料发现了如下的一种解决方法&#xff0c;个人感觉还是…

keil5.38 debug配置STlink调试,软件闪退

1.问题 keil5.38 debug配置STlink调试&#xff0c;软件闪退 2.导致的原因 因为新版的Keil加入了盗版下载器的校验机制 3.解决方法 3.1.下载旧版本STLINK文件 百度云盘 链接&#xff1a;旧版版本STLINK文件连接 提取码&#xff1a;7epc 3.2.替换掉新版编译器下的原文件 …