当前位置：首页 > 编程日记 > 正文

【ACM】杭电OJ 2063

编程日记 2024-10-16 11:40:00

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

借鉴：http://blog.sina.com.cn/s/blog_ac5ed4f30101ewjk.html

二分图（二部图）：图论中的一种特殊模型。设G(V,E)是一个无向图，如果顶点V可以分割成为两个互不相交的子集(A,B)，并且图中的每一条边(i，j)所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A ,j in B)，则称G是一个二分图。

最大匹配：给定一个二分图G，在G的一个子图M种，M的边集中任意两条边都不依附于同一顶点，则称M是一个匹配。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

增广路（增广轨或者交错轨）：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边（即已匹配和待匹配的边）在P上交替出现，则称P为相对于M的一条增广路径。（来源于二分图【百度百科】）

交替路：从一个未匹配点出发，依次经过非匹配边，匹配边，非匹配边，形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。（来源于：二分图的最大匹配、完美匹配和匈牙利算法【博客园】）

初始化：

杭电 acm 2063 ( 过山车 )

0对，无匹配

第一遍

杭电 acm 2063 ( 过山车 )

1对， a--A

第二遍
杭电 acm 2063 ( 过山车 )

2对， a--B ，b--A

第三遍
杭电 acm 2063 ( 过山车 )

3对， a--B ，b--C ，c--A

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn = 505;
int map[maxn][maxn];
int vis[maxn];
int pri[maxn];
int K,M,N;int find(int x)
{int i;for(i=1;i<=N;i++){if(vis[i]==0 && map[x][i]){vis[i]=1;if(pri[i]==-1 || find(pri[i])){pri[i]=x;return 1;}}}return 0;
}int main ()
{int k,j,i,sum;while(scanf("%d",&K)!=EOF && K){sum=0;memset(map,0,sizeof(map));memset(pri,-1,sizeof(pri));scanf("%d%d",&M,&N);for(k=1;k<=K;k++){scanf("%d%d",&i,&j);map[i][j]=1;}for(i=1;i<=M;i++){memset(vis,0,sizeof(vis));if(find(i))sum++;}printf("%d\n",sum);/*for(i=1;i<=N;i++){printf("%d %d\n",pri[i],i);}*/}return 0;
}

带注释的是输出打印查看所配对的种类

https://www.dkcj.cn/info/23287.html

AngularJs表单自动验证

angular-auto-validate 地址：https://github.com/jonsamwell/angular-auto-validate 引用： <script src"/Assets/JS/AngularJS/angular-auto-validate/dist/jcs-auto-validate.js" charset"utf-8"></script> 依赖&#…

编程日记2024/10/16 11:30:00

AlwaysVisibleControlExtender

今天早上学习了AlwaysVisibleControlExtender控件，感觉还是不错。下午就写点东西，总结一下使用方法。简单使用示例(显示当前时间) 1）在VS下，新建一个ASP.NET AJAX-Enabled Web Project项目，命名为AlwaysVisibleC…

编程日记2024/10/16 11:20:00

Depth graph

深度相机定义：可以直接获取场景中物体距离摄像头物理距离的相机。在计算机视觉系统中，三维场景信息为图像分割、目标检测、物体跟踪等各类计算机视觉应用提供了更多的可能性，而深度图像（Depth map）作为一种普遍的三维…

编程日记2024/10/16 11:10:00

【ACM】POJ 1852

【问题描述】一队蚂蚁在一根水平杆上行走，每只蚂蚁固定速度 1cm/s. 当一只蚂蚁走到杆的尽头时，立即从秆上掉落. 当两只蚂蚁相遇时它们会掉头向相反的方向前进. 我们知道每只蚂蚁在杆上的初始位置, 但是, 我们不知道蚂蚁向哪个方向前行. 你的任务是计算…

编程日记2024/10/16 11:00:00

ZStack--通过Ansible实现全自动化

2019独角兽企业重金招聘Python工程师标准>>> Agent是一种常见的IaaS软件管理设备的方式；例如，ZStack使用Python agents去管理KVM主机。因为海量的设备，安装和升级agents成为巨大的挑战，所以大多数IaaS软件把这个问题留…

编程日记2024/10/16 10:50:00

SVO 半直接视觉里程计

SVO 从名字来看，是半直接视觉里程计，所谓半直接是指通过对图像中的特征点图像块进行直接匹配来获取相机位姿，而不像直接匹配法那样对整个图像使用直接匹配。整幅图像的直接匹配法常见于RGBD传感器，因为RGBD传感器能获取整幅图像的…

编程日记2024/10/16 10:40:00

css构造文本

1. 1. 文本缩进text-indent：值；值为数字，最常用的数值单位是px(像素)，也可以直接是百分比！text-indent:100px;text-indent:10%;2. 文本对齐text-align:对其方式;可以的值为：left、center、right3. 文本行高…

编程日记2024/10/16 10:30:00

【数据结构】单链表的逆序输出（两种方法）

第一种方法：转换指针方向即：将一个已经创建好的单链表进行指针域的改变今天突然被问到单链表逆序的问题，弄了好久才看出别人的程序有啥问题，就重新写了一遍。今天才在CSDN客户端上看到美团的面试题是冒泡排序。一个看似简单…

编程日记2024/10/16 10:20:00

koa+mongoose基础入门

1.mongoose基本使用 1.安装mongodb npm install mongodb 2.引入mongodb数据表，连接mongodb，通过node来对mongodb进行异步的增删改查 const mongodb requrie(mongodb); mongodb.MongoClient.connect("mongodb://localhost/db1", function(err,…

编程日记2024/10/16 10:10:00

视觉SLAM学习（三）--------SLAM 综述

SLAM概述参考资料分享来自本人博客：https://blog.csdn.net/Darlingqiang/article/details/78840931 SLAM一般处理流程包括track和map两部分。所谓的track是用来估计相机的位姿，也叫front-end。而map部分(back-end)则是深度的构建，通过前面…

编程日记2024/10/16 10:00:00

$A_{k+1}[i][j]$

【数据结构】所有顶点对的最短路径 Floyd算法

所有顶点对的最短路径问题是指：对于给定的有向图G(V，E),求任意一对顶点之间的最短路径。可以求解得到的的递推公式： #include <stdio.h> #include <stdlib.h> const int FINITY 5000; const int M 20; typedef struct {ch…

编程日记2024/10/16 09:50:00

backbone学习总结（二）

今天来看下backbone的路由控制的功能。其实个人感觉backbone，模块就那么几个，熟悉它的框架结构，以及组成，就差不多。废话不多说，我们来看看还剩下的功能。关于路由和历史管理通过 Backbone.Router.extend 来创建路由…

编程日记2024/10/16 09:40:00

人工智能--野人过河

课程简介人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好…

编程日记2024/10/16 09:30:00

java对cookie的操作

原文：http://www.cnblogs.com/muzongyan/archive/2010/08/30/1812552.html java对cookie的操作比较简单，主要介绍下建立cookie和读取cookie，以及如何设定cookie的生命周期和cookie的路径问题。建立一个无生命周期的cookie，即随着…

编程日记2024/10/16 09:20:00

【问题描述】 Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R u…

编程日记2024/10/16 09:10:00

sparkCore源码解析之思维脑图

2019独角兽企业重金招聘Python工程师标准>>> 在学习sparkCore时，有几个模块的概念理解不是很透彻，故对照源码进行学习，并将结果一脑图的形式呈现，方便后续的持续学习。详细内容见： sparkCore源码解析之blo…

编程日记2024/10/16 09:00:00

pangilin 安装编译

make pangolin 的时候报错 ootsun:/home/sun/AR/orb/Pangolin-0.5/build# make [ 1%] Building CXX object src/CMakeFiles/pangolin.dir/log/packetstream.cpp.o /home/sun/AR/orb/Pangolin-0.5/src/log/packetstream.cpp: 在函数‘void pangolin::WaitUntilPlaybackTim…

编程日记2024/10/16 08:50:00

PHP实现求阶乘

function factorial ($x){if ($x > 1) {$s $x * factorial ($x - 1);} else {$s $x;}return $s; }$x 100;echo $x."的阶乘的为".factorial($x);转载于:https://blog.51cto.com/chensenlin/1854679

编程日记2024/10/16 08:40:00

【ACM】杭电OJ 2064（汉诺塔III）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2064 思路： 1、将n-1个盘从A移到C f(n-1)次 2、将第n个从A移到B 1次 3、将n-1个盘从C移到A f(n-1)次 4、将第n个从B移到C 1次 5、将n-1个盘从A移到C f(n-1)次 #include<cstdio> #inclu…

编程日记2024/10/16 08:30:00

文件上传至阿里云

public static String uploadFile2OSS(InputStream instream, String fileName) throws IOException {String imageName null;OSSClient ossClient null;try {ClientConfiguration conf new ClientConfiguration();// 请求超时时间设置conf.setConnectionTimeout(5000);// 请…

编程日记2024/10/16 08:20:00

ORB-SLAM2安装

安装顺利与否可能会与Ubuntu版本有关。（ubuntu16.04 gcc4.8.5这个很重要偶，本班的直接决定Pangolin能不能安装成功，如果遇到哦问题的朋友可以参考一下链接 http://blog.csdn.net/Darlingqiang/article/details/78928873）亲测可用…

编程日记2024/10/16 08:10:00

iOS 系统分析（一）阅读内核准备知识

原文出自【听云技术博客】：http://blog.tingyun.com/web/a... 0x01 iOS体系架构1.1 iOS 系统的整体体系架构用户体验( The User Experience layer )：SpringBoard 同时支持 Spotlight。应用软件开发框架（The Application Frameworks layer&a…

编程日记2024/10/16 08:00:00

【数据结构】拓扑排序

如果一个有向图中没有包含简单的回路，这样的图为有向无环图。图中的顶点代表事件（活动），图中的有向边说明了事件之间的先后关系。这种用顶点表示活动，用弧表示活动时间的优先关系的有向图称为顶点表示活动的网&#…

编程日记2024/10/16 07:50:00

Java8自定义条件让集合分组

** 将一个指定类型对象的集合按照自定义的一个操作分组； 每组对应一个List、最终返回结果类型是:List<List<T>> param <T>*/static class GroupToList<T> implements Collector<T, List<List<T>>, List<List<T>&g…

编程日记2024/10/16 07:40:00

ROS_Kinetic ubuntu 16.04

ROS_Kinetic系列学习(一)，在ubuntu 16.04安装ROS Kinetic。 http://wiki.ros.org/kinetic/Installation/Ubuntu 通过网页快速了解Linux（Ubuntu）和ROS机器人操作系统，请参考实验楼在线系统如下： 纯净定制版镜像已经…

编程日记2024/10/16 07:30:00

android 获取手机GSM/CDMA信号信息,并获得基站信息

本文转自：http://software.intel.com/zh-cn/blogs/2011/12/16/android-gsmcdma/ 在Android中我们常用的轻松获取WIFI信号列表，那如何获取CDMA或者GSM的手机信号呢？系统提供了TelephonyManager类，此类非常丰富，基本你所…

编程日记2024/10/16 07:20:00

$e(i)$