hdu 4862 KM算法 最小K路径覆盖的模型

时间:2022-09-18 23:58:33

http://acm.hdu.edu.cn/showproblem.php?pid=4862

选t<=k次,t条路要经过全部的点一次而且只一次。

建图是问题:

我自己最初就把n*m 个点分别放入X集合以及Y集合,再求最优匹配,然后连例子都过不了,并且事实上当时解释不了什么情况下不能得到结果。由于k此这个条件相当于没用上。。。

建图方法:

1、X集合和Y集合都放入n*m+k个点,X中前n*m个点和Y中前n*m个点之间。假设格子里的值相等。权就是(收益-耗费),不等就是(-耗费),由于要的是最大收益,所以初始时。全部点之间权值为-1;

原因:例如以下图,1->2  2->3  3->1   二分图的边本身不和其它边相连,可是这种建图方式,使得能够找到连同路径1->2->3

由此学到的一种思维方式:二分图又称作二部图。是图论中的一种特殊模型。 设G=(V,E)是一个无向图。假设顶点V可切割为两个互不相交的子集(A,B),而且图中的每条边(i。j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)。则称图G为一个二分图。可是假设两个子集是一样的。那么就能通过二分图的算法找路径或者连通分量

  

这样建图须要避免的是1->1,这样的自环的情况。导致有些点不能被覆盖,避免的方法就是初始化的时候,由于要的是最大收益。所以把自环的边初始化为最小值。

hdu 4862   KM算法  最小K路径覆盖的模型

2、X中后k个点到Y中前n*m个点,权值为0。Y中后k个点到X中前n*m个点,权值也为0。增加的k个点是作为起点和终点,起点到第一个格子不须要耗费

3、X中k个点和Y中k个点一一相应的权值为0  由于同意少于k次把图遍历完毕。k个点中,有自环,说明这次不须要用

建图说的应该够清了,以后复习也好用

帖代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string> using namespace std; #define rep(i,s,e) for(int i=s;i<e;i++) const int INF = 999999;//
const int MAXN = 11*11+150;
int n,matv[MAXN][MAXN],mat[MAXN][MAXN],match[MAXN];
bool sx[MAXN],sy[MAXN];
int lx[MAXN],ly[MAXN];
char line[MAXN]; inline int ABS(int x)
{
return x>=0?x:-x;
} bool path(int u)
{
sx[u]=true;
rep(v,0,n)
if(!sy[v] && lx[u]+ly[v]==mat[u][v])
{
sy[v]=1;
if(match[v]==-1 || path(match[v]))
{
match[v]=u;
return true;
}
}
return false;
} int KM()
{
rep(i,0,n)
{
lx[i]=-INF;
ly[i]=0;
rep(j,0,n)
{
lx[i]=max(lx[i],mat[i][j]);
}
}
memset(match, 0xff, sizeof(match));
rep(u,0,n)
{
while(1)
{
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
if(path(u))break;
int dmin=INF;
rep(i,0,n)
if(sx[i])
rep(j,0,n)
if(!sy[j])
dmin=min(lx[i]+ly[j]-mat[i][j],dmin);
rep(i,0,n)
{
if(sx[i])
lx[i]-=dmin;
if(sy[i])
ly[i]+=dmin;
}
}
}
int sum=0;
rep(j,0,n)////
{
if(mat[match[j]][j] == -INF)return -INF;
sum+=mat[match[j]][j];
}
return sum;
} void init(int nn, int mm,int kk)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
mat[i][j]=-INF;
}
rep(i,nn*mm,n)
mat[i][i]=0;
rep(i,0,nn)
rep(j,0,mm)
{
rep(ii,0,kk)
mat[nn*mm+ii][i*mm+j]=mat[i*mm+j][nn*mm+ii]=0;
//right
rep(jj,j+1,mm)
{
if(matv[i][j] == matv[i][jj])
{
mat[i*mm+j][i*mm+jj]=matv[i][j]-ABS(j-jj)+1;
}
else
{
mat[i*mm+j][i*mm+jj]=-ABS(j-jj)+1;
}
}
//below
rep(ii,i+1,nn)
{
if(matv[i][j] == matv[ii][j])
{
mat[i*mm+j][ii*mm+j]=matv[i][j]-ABS(i-ii)+1;//变量写错。。。 }
else
{
mat[i*mm+j][ii*mm+j]=-ABS(i-ii)+1;
}
}
}
} int main()
{
//freopen("hdu4862.txt","r",stdin);
//freopen("out.txt","w",stdout);
int ncase;
int nn,kk,mm;
scanf("%d",&ncase);
for(int icase=1;icase<=ncase;icase++)
{
scanf("%d%d%d",&nn,&mm,&kk);
n=nn*mm+kk;
rep(i,0,nn)
{
scanf("%s",line);
rep(j,0,mm)
{
matv[i][j]=line[j]-'0';
}
}
init(nn,mm,kk);
int ans=KM();
if(ans<=-INF)printf("Case %d : -1\n",icase);
else printf("Case %d : %d\n", icase, ans);
}
return 0;
}

hdu 4862 KM算法 最小K路径覆盖的模型的更多相关文章

  1. HDU 4862 Jump(最小K路径覆盖)

    输入一个n×m网格图,每个结点的值为0-9,可以从任意点出发不超过k次,走完每个点且仅访问每个结点一次,问最终的能量最大值.不可全部走完的情况输出-1. 初始能量为0. 而结点(x,y)可以跳跃到结点 ...

  2. 网络费用流-最小k路径覆盖

    多校联赛第一场(hdu4862) Jump Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Ot ...

  3. hdu 3488&lpar;KM算法&vert;&vert;最小费用最大流&rpar;

    Tour Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submis ...

  4. hdu 3395&lpar;KM算法&vert;&vert;最小费用最大流&lpar;第二种超级巧妙&rpar;&rpar;

    Special Fish Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  5. Air Raid POJ - 1422 【有向无环图(DAG)的最小路径覆盖【最小不相交路径覆盖】 模板题】

    Consider a town where all the streets are one-way and each street leads from one intersection to ano ...

  6. P2172 &lbrack;国家集训队&rsqb;部落战争 二分图最小不相交路径覆盖

    二分图最小不相交路径覆盖 #include<bits/stdc++.h> using namespace std; ; ; ; ], nxt[MAXM << ], f[MAXM ...

  7. Antenna Placement(匈牙利算法 ,最少路径覆盖)

    Antenna Placement Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6991   Accepted: 3466 ...

  8. POJ Air Raid 【DAG的最小不相交路径覆盖】

    传送门:http://poj.org/problem?id=1422 Air Raid Time Limit: 1000MS   Memory Limit: 10000K Total Submissi ...

  9. HDU 2255 KM算法 二分图最大权值匹配

    奔小康赚大钱 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Subm ...

随机推荐

  1. 运行sql server profiler所需的权限

    ********运行Sql Server Profiler所需的权限(performance)*********/ --EG. -- 使用TRACE帐户(Performancetest)跟踪Sql S ...

  2. 3&period;jsp基本语法笔记

    1.page标签 <%@ page language="java" import="java.util.*" contentType="text ...

  3. java中的分支结构 switch case的使用

    switch(A),括号中A的取值只能是整型或者可以转换为整型的数值类型,比如byte.short.int.char.string(jdk1.7后加入)还有枚举:需要强调的是:long是不能用在swi ...

  4. Solr 5&period;5&period;0 &plus; tomcat 7&period;0&period;69 &plus; zookeeper-3&period;4&period;6 Cloud部署

    Solr介绍:Solr是一个独立的企业级搜索应用服务器,Solr基于Lucene的全文搜索服务器,同时对其进行了扩展,提供了比Lucene更为丰富的查询语言,同时实现了可配置.可扩展并对查询性能进行了 ...

  5. linux-python3&period;8安装

    环境:  centos7.5 版本:python3.8 1.依赖包安装 yum -y install zlib-devel bzip2-devel openssl-devel ncurses-deve ...

  6. 使用nvm安装node&comma;全局npm&comma;cnpm

    1.nvm-windows下载 下载地址https://github.com/coreybutler/nvm-windows/releases,下载nvm-setup.zip 2.安装nvm 首先把n ...

  7. C&num; CEF 封装UserControl

    using System; using System.Collections.Generic; using System.ComponentModel; using System.Drawing; u ...

  8. 转 DataTorrent 1&period;0每秒处理超过10亿个实时事件

    DataTorrent是一个实时的流式处理和分析平台,它每秒可以处理超过10亿个实时事件. 与Twitter平均每秒大约6000条微博相比,最近发布的DataTorrent 1.0似乎已经超出了需求, ...

  9. Mysql5&period;7的gtid主从半同步复制和组复制

    (一)gtid主从半同步复制 一.半同步复制原理 mysql默认的复制是异步的,主库在执行完客户端提交的事务后会立即将结果返回给客户端,并不关心从库是否已经接收并处理,这样就会有一个问题,主库如果cr ...

  10. &lbrack;转&rsqb;blocks编程

    原文地址:http://geeklu.com/2012/01/block/ 介绍 声明创建和调用 Block和变量 Block实际应用 1.介绍 Block是一个C Level的语法以及运行时的一个特 ...