专栏首页Zaqdt_ACMHDU 3488 Tour(拆点+二分图最大权匹配--KM)

HDU 3488 Tour(拆点+二分图最大权匹配--KM)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

       题意是有n个城市,m条边,这个图中有一个或者多个环,问要覆盖所有的点,选那几个环的总权值最小。

       因为是有向环,所以每个点的入度和出度都是1,所以就符合了二分图的性质,我们就需要把每个点拆成两个点,一个表示入度一个表示出度,然后求二分图的最佳匹配就行了,因为要求权值的最小和,我们就需要把权值取负数,然后计算最大权,然后再对结果取负就好了。


AC代码:

#include <bits/stdc++.h>
#define maxn 305
#define inf 0x7fffffff
using namespace std;
int w[maxn][maxn];
int pre[maxn], cx[maxn], cy[maxn];
bool usex[maxn], usey[maxn];
int n,m,ans;

void init(){
  memset(cy, 0, sizeof(cy));
  memset(cx, 0, sizeof(cx));
  memset(w, -0x3f3f, sizeof(w));
  memset(pre, -1, sizeof(pre));
}

bool dfs(int u){
  usex[u] = true;
  for(int v=1;v<=n;v++){
    if(usey[v] == false && cx[u] + cy[v] == w[u][v]){
      usey[v] = true;
      if(pre[v] == -1 || dfs(pre[v])){
        pre[v] = u;
        return true;
      }
    }
  }
  return false;
}

int km(){
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cx[i] = max(cx[i], w[i][j]);
    }
  }
  for(int i=1;i<=n;i++){
    while(true){
      int d = inf;
      memset(usex, false, sizeof(usex));
      memset(usey, false, sizeof(usey));
      if( dfs(i) ) break;

      for(int j=1;j<=n;j++){
        if(usex[j] == true){
          for(int k=1;k<=n;k++){
            if(usey[k] == false) d = min(d, cx[j] + cy[k] - w[j][k]);
          }
        }
      }
      if(d == inf) return -1;

      for(int j=1;j<=n;j++) if(usex[j] == true) cx[j] -= d;
      for(int j=1;j<=n;j++) if(usey[j] == true) cy[j] += d;
    }
  }
  ans = 0;
  for(int i=1;i<=n;i++){
    ans += w[pre[i]][i];
  }
  return ans;
}

int main()
{
  int T;
  scanf("%d",&T);
  while(T--){
    init();
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
      int u,v,ww;
      scanf("%d%d%d",&u,&v,&ww);
      w[u][v] = max(w[u][v], -ww);
    }
    printf("%d\n", -km());
  }
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #543 (Div. 2, based on Technocup 2019 Final Round) A. Technogoblet of Fire(思维)

    题目链接:https://codeforces.com/contest/1121/problem/A

    Ch_Zaqdt
  • 最少联通代价(dfs+曼哈顿距离)

    现在要把这 2 个连通块连通, 求最少需要把几个’.’转变成’X’。上图的例子中, 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点...

    Ch_Zaqdt
  • HDU 2255 奔小康赚大钱(二分图最佳匹配--KM算法)

            二分图带全匹配的裸题,直接贴板子就行,对于二分图最佳匹配可以用网络流去写,还有KM算法也可以解决这个问题,这个算法的中心思想就是依次选择最大权的...

    Ch_Zaqdt
  • 【C语言笔记】函数参数压栈的顺序?

    按照日常习惯来看,C语言的函数参数压栈顺序是从左到右吧?但是事实却是相反的,C语言函数参数压栈顺序是从右到左的。下面看一个程序:

    正念君
  • BZOJ4300: 绝世好题(dp)

    给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。

    attack
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 【CodeForces 620D】Professor GukiZ and Two Arrays

    两个数列,一个有n个数,另一个有m个数,让你最多交换两次两个数列的数,使得两个数列和的差的绝对值最小,求这个差的绝对值、最少交换次数、交换数对

    饶文津
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • 「2017 Multi-University Training Contest 2」2017多校训练2

    给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[...

    饶文津

扫码关注云+社区

领取腾讯云代金券