HUD3488 Tour(二分图的最小权值和)

2023-11-11 12:08

本文主要是介绍HUD3488 Tour(二分图的最小权值和),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:

给你一个有向图,边有权值,现在要你求若干个环包含所有的顶点,并且每个顶点只出现一次(除了起点),求所有环中所有边得权值之和最小值。

要点:

因为每个顶点只出现一次,干脆所有环都拆成起点到一个点再回起点,这样就是一个二分图的最小权值和问题。前面做的题都是求最大权值和,最小权值和就是将每条边的权值取负,其他的都不用变(除了lx的取最大值),最后输出再取负即可。


171460162016-05-13 16:36:37Accepted3488140MS1880K1742 BC++seasonal

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 205
#define inf 0x3f3f3f3f
bool sx[N], sy[N];
int lx[N], ly[N],w[N][N],girl[N];
int slack[N];
int n, m;void init()
{for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)w[i][j] = -inf;
}
bool find(int u)
{int v, t;sx[u] = true;for (v = 1; v <= n; v++){if (sy[v])continue;t = lx[u] + ly[v] - w[u][v];if (t == 0){sy[v] = true;if (girl[v] == -1 || find(girl[v])){girl[v] = u;return true;}}elseslack[v] = min(slack[v], t);}return false;
}
int km()
{int i,j;memset(girl, -1, sizeof(girl));memset(ly, 0, sizeof(ly));for (int i = 1; i <= N; ++i){//lx[i] = -inf;注意最大权的模板中的这里不用写for (int j = 1; j <= N; ++j)lx[i] = max(lx[i], w[i][j]);}for (i = 1; i <= n; i++){memset(slack, inf, sizeof(slack));while (1){memset(sx, false, sizeof(sx));memset(sy, false, sizeof(sy));if (find(i))break;int d = inf;for (j = 1; j <= n; j++)if (!sy[j])d = min(d, slack[j]);for (j = 1; j <= n; j++)if (sx[j])lx[j] -= d;for (j = 1; j <= n; j++){if (sy[j])ly[j] += d;elseslack[j] -= d;}}}int sum = 0;for (i = 1; i <= n; i++)if (girl[i] != -1)sum += w[girl[i]][i];return sum;
}int main()
{int t,x,y,value;scanf("%d", &t);while (t--){init();scanf("%d%d", &n, &m);while (m--){scanf("%d%d%d", &x, &y, &value);w[x][y] = max(w[x][y], -value);//求最小权值就直接把权值改成负数求最大即可}printf("%d\n", -km()); //最后取负输出即可}return 0;
}


这篇关于HUD3488 Tour(二分图的最小权值和)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c