网站开发去哪里找程序员,重庆城乡规划和建设局网站,番禺区网站设计,衡水网站设计文章目录titlesolutioncodetitle
solution
读完翻译后#xff0c;很明显就是个朱刘算法的板子题 最小树形图#xff0c;就是给出一个带权有向图 从中指定一个特殊的结点 root 求一棵以 root 为根的有向生成树 T#xff0c;且使得 T 中所有边权值最小 简单来说#xff0c…
文章目录titlesolutioncodetitle
solution
读完翻译后很明显就是个朱刘算法的板子题 最小树形图就是给出一个带权有向图 从中指定一个特殊的结点 root 求一棵以 root 为根的有向生成树 T且使得 T 中所有边权值最小 简单来说最小树形图就是有向图的最小生成树 朱刘算法分为四个过程 1求最短弧集合 E
集合E对于每个点viv_ivi根除外viv_ivi的入边最小权值in[vi]in[v_i]in[vi]所构成的集合
2判断集合 E 中有没有有向环如果有转步骤 3否则转步骤 4
3收缩点把有向环收缩成一个点并且对图重新构建包括边权值的改变和点的处理之后再转步骤 1
权值改变方式 1.该边两个点属于同一个环——权值保持不变 2.该边两个点属于不同环——权值➖边的入点(即有向边指向的那个点vvv的最小入边权值in[v]in[v]in[v]
4展开收缩点求得最小树形图
code
#include cmath
#include cstdio
#include cstring
using namespace std;
#define MAXN 105
#define inf 0x3f3f3f3f
struct node {int u, v;double w;node(){}node( int U, int V, double W ) {u U, v V, w W;}
}edge[MAXN * MAXN];
double x[MAXN], y[MAXN], in[MAXN];
int vis[MAXN], id[MAXN], pre[MAXN];double pigcow( int rt, int n, int m ) {memset( id, 0, sizeof( id ) );double ans 0;while( 1 ) {for( int i 1;i n;i ) in[i] inf;for( int i 1;i m;i ) {int u edge[i].u, v edge[i].v;double w edge[i].w;if( w in[v] u ! v )pre[v] u, in[v] w;} for( int i 1;i n;i ) {if( i rt ) continue;if( in[i] inf ) return -1;}int cnt 0;in[rt] 0;memset( id, 0, sizeof( id ) );memset( vis, 0, sizeof( vis ) ); for( int i 1;i n;i ) {ans in[i];int t i;while( vis[t] ! i ! id[t] t ! rt )vis[t] i, t pre[t];if( t ! rt ! id[t] ) { cnt;for( int fa pre[t];fa ! t;fa pre[fa] )id[fa] cnt;id[t] cnt;}}if( ! cnt ) break;for( int i 1;i n;i )if( ! id[i] ) id[i] cnt;for( int i 1;i m;i ) {int u edge[i].u, v edge[i].v;edge[i].u id[u], edge[i].v id[v];if( id[u] ! id[v] ) edge[i].w - in[v];}n cnt;rt id[rt];}return ans;
}double calc( int u, int v ) {return sqrt( ( x[u] - x[v] ) * ( x[u] - x[v] ) ( y[u] - y[v] ) * ( y[u] - y[v] ) );
}int main() {int n, m;while( ~ scanf( %d %d, n, m ) ) {for( int i 1;i n;i )scanf( %lf %lf, x[i], y[i] ); for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );edge[i] node( u, v, calc( u, v ) );}double ans pigcow( 1, n, m );if( ans ! -1 ) printf( %.2f\n, ans );else printf( poor snoopy\n );}return 0;
} 其实就是为了存个板子哈哈哈哈哈
