首页 > 其他分享 >题解:P5934 [清华集训2012] 最小生成树

题解:P5934 [清华集训2012] 最小生成树

时间:2024-08-27 10:06:25浏览次数:14  
标签:nxt P5934 val int 题解 边权 dep num 2012

主要思路:网络流。

思路

先考虑最小生成树,如果一条边边权大于等于选中的边,那么这条边是否删去没有任何影响。

按边权排序,对于边 \((u,v,L)\),若要加上当且仅当 \(u\) 和 \(v\) 并不联通。

把所有边权比选定的边的边权小的边拿出来连上,流量均为 \(1\),最小割。

最大树同理,连上边权比选定的边的边权大的边,接着跑最大流。

两次答案相加。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9 + 7;
struct node {
	int nxt, to, val;
} e[3000005];
int num = 1, h[250000], s, t;
void add(int from, int to, int dis) {
	e[++num].nxt = h[from],e[num].to = to,e[num].val = dis,h[from] = num,e[++num].nxt = h[to],e[num].to = from,e[num].val = 1,h[to] = num;
}
queue<int>q;
int n, m, ans, dep[250000];
int u[2500000], v[2500000], w[2500000], l;
bool bfs(int s,int t){
	memset(dep,0x3f,sizeof(dep));
	while(!q.empty())q.pop();
	dep[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dep[v]>inf&&e[i].val){
				dep[v]=dep[u]+1;
				q.push(e[i].to);
			}
		}
	}
	if(dep[t]<inf)return 1;
	return 0;
}
int dfs(int u,int t,int lim){
	if(!lim||t==u)return lim;
	int flow=0,f;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		int &w=e[i].val;
		if(dep[v]==dep[u]+1&&(f=dfs(v,t,min(lim,w)))){
			flow+=f;
			lim-=f;
			w-=f;
			e[i^1].val+=f;
			if(!lim)break;
		}
	}
	return flow;
}
void dinic(int s, int t) {
	while (bfs(s, t))ans += dfs(s, t, inf);
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)cin >> u[i] >> v[i] >> w[i];
	cin >> s >> t >> l;
	for (int i = 1; i <= m; i++)if (w[i] < l)add(v[i], u[i], 1);
	dinic(s, t);
	memset(h,0,sizeof(h));
	num=1;
	for(int i=1;i<=m;i++)if(w[i]>l)add(v[i],u[i],1);
	dinic(s,t);
	cout<<ans;
	return 0;
}

标签:nxt,P5934,val,int,题解,边权,dep,num,2012
From: https://www.cnblogs.com/aub-unluck-beginning/p/18382078

相关文章

  • 题解:P11007 『STA - R7』Odtlcsu
    评价:简单构造。思路注意题目中的“如果有多解输出任意一种即可”。由于\(a\)与\(a^{2}\)的奇偶性必定是一致的,所以我们可以将情况分为两种。当\(x\)与\(y\)奇偶性不一致时,但由于\(a\)与\(a^{2}\)的奇偶性必定是一致的,所以始终无法构造出正确的序列。但注意题目......
  • P4126 [AHOI2009] 最小割 题解
    DescriptionA,B两个国家正在交战,其中A国的物资运输网中有\(N\)个中转站,\(M\)条单向道路。设其中第\(i\(1\leqi\leqM)\)条道路连接了\(u_i,v_i\)两个中转站,那么中转站\(u_i\)可以通过该道路到达\(v_i\)中转站,如果切断这条道路,需要代价\(c_i\)。现在B国想找出一个......
  • 最大矩阵区间 题解
    题意简述给定\(n\)行\(m\)列矩阵\(A\)。对于每一行\(i\),选择非空区间\([l_i,r_i]\),满足\(\foralli\in[1,n)\),\([l_i,r_i]\)和\([l_{i+1},r_{i+1}]\)相交,即\(\max\{l_i,l_{i+1}\}\leq\min\{r_i,r_{i+1}\}\)。求所有选出区间的\(A_{i,j}\)值......
  • Luogu P4588 数学运算 题解 [ 绿 ] [ 线段树 ]
    LuoguP4588数学运算。虽然是一个很典的题,但里面的思想还是比较值得记录的。假做法一开始看到此题还以为是乘法逆元的模板题,但看到\(m\)与\(M\)不互质,就知道这种做法是假的了。注意exgcd虽然能求模数为合数的逆元,但是要是两数不互质就什么算法都搞不了了。因此,本题不能......
  • Luogu P7250 BalticOI 山峰 题解 [ 蓝 ] [ 模拟 ] [ 并查集 ] [ BFS ]
    LuoguP7250BalticOI山峰。一道大模拟,很暴力,也很难写。建议紫或蓝,标签为模拟、广度优先搜索、并查集。思路首先观察到答案取决于路线上的最低点,所以我们可以把所有点的高度丢进一个桶里,从大到小枚举,尝试更新答案。这应该是个挺经典的trick了。感性理解可以看作所有山都先......
  • 题解:P9256 [PA 2022] Muzyka pop 2
    题解:P9256[PA2022]Muzykapop2题目传送门题目重点从前往后比较,和数字比较一样,如:12345<12445。如果一个串是另一个串的前缀,那么不是前缀串的那个字典序小。题目思路我爱贪心贪心就行了,每次让x增加1,找出1的个数来实现。要求序列是字典序最小的,因此每次选择尽可......
  • 动态dp——P8820 [CSP-S 2022] 数据传输 题解
    P8820[CSP-S2022]数据传输可怜的cnblog被(昨天DDos+今天CC)攻击了(望周知!),只好先发在CSDN题面:题目描述小C正在设计计算机网络中的路由系统。测试用的网络总共有nn......
  • 【跨域问题解决】Access to XMLHttpRequest at xxx from origin xxx has been blocked
    这个错误是由于浏览器的同源策略(CORS,Cross-OriginResourceSharing)导致的。当从一个源(origin)向另一个源请求资源时,如果这两个源的协议、域名或端口号不同,就会触发CORS策略。解决方法要解决这个问题,你需要在你的后端服务中添加CORS支持,以便它允许来自你的请求。这通常......
  • [ARC182C] Sum of Number of Divisors of Product 题解
    题目链接点击打开链接题目解法我怎么不会分治/fn首先把\(x\)分解成\(\prodp_i^{x_i}(0\lei\le5)\)的形式,正因数个数为\(\prod(x_i+1)\)有一个很牛的想法是:合并两个\(x_i\)序列(假设一个叫\(x_0,...,x_5\),另一个叫\(y_0,...,y_5\))先不考虑后面的\(+1\)(可以最后......
  • 题解:AT_arc183_b [ARC183B] Near Assignment
    题意:给你长度为\(N\)的整数序列\(A,B\)以及整数\(K\)。你可以执行下列操作零次或多次。选择整数\(i\)和\(j\)(\(1\leqi,j\leqN\))。这里,\(|i-j|\leqK\)必须保持不变。然后,将\(A_{i}\)的值改为\(A_{j}\)。判断是否有可能使\(A\)与\(B\)相同。分......