BZOJ2521[SHOI2010] 最小生成树
原题链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2521
最小生成树
Description
Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外,他还知道,某一个图可能有多种不同的最小生成树。例如,下面图 3中所示的都是图 2中的无向图的最小生成树:
当然啦,这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB,至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中,你可以对这个无向图进行操作,一次单独的操作是指:先选择一条图中的边 P1P2,再把图中除了这条边以外的边,每一条的权值都减少1。如图 4所示就是一次这样的操作:
Input
输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。
接下来m行依次描述标号为1,2,3…m的无向边,每行描述一条边。每个描述包含3个整数x、y、d,表示这条边连接着标号为x、y的点,且这条边的权值为d。
输入文件保证1<=x,y<=N,x不等于y,且输入数据保证这个无向图一定是一个连通图。
Output
输出文件只有一行,这行只有一个整数,即,使得标号为Lab边一定出现最小生成树中的最少操作次数。
Sample Input
4 6 1
1 2 2
1 3 2
1 4 3
2 3 2
2 4 4
3 4 5
Sample Output
1
HINT
第1个样例就是问题描述中的例子。
1<=n<=500,1<=M<=800,1<=D<10^6
题解
首先,显然的是:把其他边 −1 − 1 的操作等价于把这条边 +1 + 1 。
要将某个边 (u,v) ( u , v ) 强制加入最小生成树中,就要把其他可以取代这条边的边的权值加到 val(u,v)+1 v a l ( u , v ) + 1 。
那么,我们要做的就是用 val(u,v)+1−val(其他) v a l ( u , v ) + 1 − v a l ( 其 他 ) 的代价删掉一些边,使 u,v u , v 不连通,就可以将边 (u,v) ( u , v ) 加入最小生成树里。
最小割???
代码
注意无向图的加边,没有正反向边之分。
#include<bits/stdc++.h>
using namespace std;
const int M=505;
struct sd{int to,fl;}ed[M<<2];
struct hh{int a,b,d;}data[M<<2];
int n,m,lab,id,start,end,lay[M],itr[M];
vector<int>mmp[M];
queue<int>dui;
void add(int a,int b,int d)
{
mmp[a].push_back(id);ed[id++]=(sd){b,d};
mmp[b].push_back(id);ed[id++]=(sd){a,d};
}
void in()
{
scanf("%d%d%d",&n,&m,&lab);
for(int i=1;i<=m;++i)scanf("%d%d%d",&data[i].a,&data[i].b,&data[i].d);
start=data[lab].a,end=data[lab].b;
for(int i=1;i<=m;++i)if(data[i].d<=data[lab].d&&i!=lab)add(data[i].a,data[i].b,data[lab].d-data[i].d+1);
}
int bfs(int s,int e)
{
memset(lay,0,sizeof(lay));
memset(itr,0,sizeof(itr));
int f,to,fl,hh;
lay[s]=1;dui.push(s);
while(!dui.empty())
{
f=dui.front();dui.pop();
for(int i=mmp[f].size()-1;i>=0;--i)
{
hh=mmp[f][i];to=ed[hh].to;fl=ed[hh].fl;
if(lay[to]||!fl)continue;
lay[to]=lay[f]+1;dui.push(to);
}
}
return lay[e];
}
int dfs(int s,int e,int mn)
{
if(!mn||s==e)return mn;
int ans=0,to,fl,hh,tmp,siz=mmp[s].size()-1;
for(int i=itr[s];i<=siz;++i)
{
hh=mmp[s][i];to=ed[hh].to;fl=ed[hh].fl;
if(lay[to]!=lay[s]+1||!fl)continue;
tmp=dfs(to,e,min(mn-ans,fl));
if(!tmp)continue;
ed[hh].fl-=tmp;ed[hh^1].fl+=tmp;
ans+=tmp;itr[s]=i;
if(mn==tmp)break;
}
return ans;
}
void ac()
{
int ans=0;
while(bfs(start,end))ans+=dfs(start,end,INT_MAX);//puts("GG");
printf("%d",ans);
}
int main(){in();ac();}
相关文章
- 【图论——第七讲】Pirm算法求最小生成树问题及其堆优化
- Poj 3522 最长边与最短边差值最小的生成树
- 李宏毅机器学习_11-0深度生成模型(上下)
- 【BZOJ1083】[SCOI2005]繁忙的都市(最小生成树)
- 【BZOJ4883】棋盘上的守卫(最小生成树)
- Vivado两种生成、固化烧录文件
- 【BZOJ1937】[Shoi2004]Mst 最小生成树 KM算法(线性规划)
- 图的最小生成树:Prim算法--解锁一批边,解锁一批节点
- C#,最小生成树(MST)克鲁斯卡尔(Kruskal)算法的源代码
- C#,最小生成树(MST)博鲁夫卡(Boruvka)算法的源代码
- Vue - H5 生成带二维码和文案的宣传海报(可自定义二维码扫描后的内容、海报背景图、文案文字、宽高间距等)用 HTML 写可 DIY 的海报,做完后转为图片供用户保存和转发下载
- 如何快速生成openwrt的差异配置项
- IDEA怎么生成UML类图
- wav 格式音频文件生成例子
- Java生成二维码
- Freckles (最小生成树)
- 【POJ 2485】Highways(Prim最小生成树)
- 最小生成树(二)Prim算法
- selenium之批量执行测试用例生成HTML结果文件
- 【Unity3D日常开发】生成预制体,并且预制体自动销毁
- 用laravel生成sitemap
- 贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)
- 基于keras4bert的seq2seq机制的文章标题生成
- 24最小生成树之Prim算法
- Java使用位图+redis生成抖音号、淘淘号、B站UID号等分布式ID
- php随机生成汉字实现方法
- 服务器集群自动化部署工具,自动生成 Redis+Tomcat+Nginx相关需要文件,自动配置好依赖jar包和配置文件,简单快速搭建集群环境
- vscode 快速生成html模板代码的几种方式
- 【bzoj2561】最小生成树 网络流最小割
- 小程序生成带推荐码(场景id)的二维码