SGU 206 Roads KM算法 匹配模型的转化

2023-11-08 08:58

本文主要是介绍SGU 206 Roads KM算法 匹配模型的转化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这是一道非常好的题目

题目大意:

给了一个图,n个点,m条边,其中前n-1条边保证是生成树,现在你可以修改每条边的边权,花费为修改量,然后用最小的花费修改使得前n-1条边为最小生成树

这题乍一看无从下手

实际上可以这么分析

边可以分为两类,一种是前n-1条边,构成了一个生成树,其他的边是另外一种边

显然如果我们要达到最小生成树的目的,就要让生成树上的边变小,而另外的边变大

从第n条边到第m条边,每条边如果加入那个生成树中,必然会构成了一个环,而我们不想让这条边去替换环中的任意一条边,所以这条边必须比任意环中的边要大。

假设环中的某边为i,这条边为j, 权值分为w[i], w[j] ,修改后的权值为 w[i] - x[i] , w[j] + x[j] 必然有 w[i] - x[i] <= w[j] + x[j]  从而有 x[i] + x[j] >= w[i] - w[j] 

然后目的是sum(x[i]) 1 <= i <= m   最小         

观察x[i] + x[j] >= w[i] - w[j] 这个不等式和我们的目的,是否发现跟KM算法有相像之处?

因为由可行点标的的定义,图中的任意一个完全匹配,其边权总和均不大于所有点的标号之和,而仅由可行边组成的完全匹配的边权总和等于所有点的标号之和

而我们在寻找可行边的过程,每条边从不是可行边到变为可行边,会使边两端的可行顶标之和减小,最后到达最大权匹配时就是顶标和最小的时候。

这道题又像我们传达了一个算法活用的思想。

往往根据几个式子,就可以转化为某个模型。这也是建立在对算法的深刻理解上吧、

注意:如果两边点数不知谁大谁小,点数少的那一方补齐点,补的点跟另一方的点的边权都为0,KM是先保证的最大匹配数,再保证的最大权

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 405
#define MAXM 405
#define INF 100000007
using namespace std;
int n, m, ny, nx;
int w[MAXN][MAXM];
int lx[MAXN], ly[MAXM];
int linky[MAXM];
int visx[MAXN], visy[MAXM];
int slack[MAXM];
bool find(int x)
{visx[x] = 1;for(int y = 1; y <= ny; y++){if(visy[y]) continue;int t = lx[x] + ly[y] - w[x][y];if(t == 0){visy[y] = 1;if(linky[y] == -1 || find(linky[y])){linky[y] = x;return true;}}else if(slack[y] > t) slack[y] = t;}return false;
}
int KM()
{memset(linky, -1, sizeof(linky));for(int i = 1; i <= nx; i++) lx[i] = -INF;memset(ly, 0, sizeof(ly));for(int i = 1; i <= nx; i++)for(int j = 1; j <= ny; j++)if(w[i][j] > lx[i]) lx[i] = w[i][j];for(int x = 1; x <= nx; x++){for(int i = 1; i <= ny; i++) slack[i] = INF;while(true){memset(visx, 0, sizeof(visx));memset(visy, 0, sizeof(visy));if(find(x)) break;int d = INF;for(int i = 1; i <= ny; i++)if(!visy[i]) d = min(d, slack[i]);if(d == INF) return -1;for(int i = 1; i <= nx; i++)if(visx[i]) lx[i] -=d;for(int i = 1; i <= ny; i++)if(visy[i]) ly[i] += d;else slack[i] -= d;}}return 1;
}
int x[MAXN], y[MAXN], z[MAXN];
int g[MAXN][MAXN];
int dfs(int pre, int u, int v, int id)
{if(u == v) return 1;for(int i = 1; i <= n; i++){if(pre == i || !g[u][i]) continue;if(dfs(u, i, v, id)){w[g[u][i]][id] = z[g[u][i]] - z[id];return 1;}}return 0;
}
int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]);for(int i = 1; i <= n - 1; i++) g[x[i]][y[i]] = g[y[i]][x[i]] = i;for(int i = 1; i <= m; i++)for(int j = 1; j <= m; j++)w[i][j] = 0;nx = ny = m;for(int i = n; i <= m; i++)dfs(0, x[i], y[i], i);KM();for(int i = 1; i < n; i++) printf("%d\n", z[i] - lx[i]);for(int i = n; i <= m; i++) printf("%d\n", z[i] + ly[i]);return 0;
}



这篇关于SGU 206 Roads KM算法 匹配模型的转化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/368910

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (