HDU 1350 Taxi Cab Scheme

By NodeKey in ACM on

题意： 老司机接客的故事 有很多顾客想要去一些地方 给你起点和终点 问最少需要多少老司机 （起点不计时 主要是坐标建图还是第一次写到 就写个题解压压惊 其实还是按照题意来就好了 再用数组链表实现邻接表存图 好像写烦了 慢了点 #include #include #include #include #include using namespace std; const int maxn=505; int n,cnt; int head[maxn],link[maxn]; bool vis[maxn]; struct point { int x,y; }; inline int dist(const point& a,const point& b) { return…

HDU 1498 50 years, 50 colors

By NodeKey in ACM on

尽管是大水题 但是再怎么说就是自己走过的路啊 不过现在只是二分图入门阶段 到现在为止接触的一些题目真的是太水了 只要 吧题目理解 套个模板就好了 所以这里就只拿一个hdu1498作为水题典例 简单说 题目是个最小点覆盖问题 二分图的最小点覆盖==最大匹配数 问的是哪些数字在k步操作内无法完全覆盖 也就是说最大匹配大于k的有哪些 AC Code #include #include #include #include #include #include #include using namespace std; const int maxn=105; int n,k; int g[maxn][maxn],link[maxn]; bool vis[maxn]; set kao; int hungary(int); bool dfs(int,…

FZU 2039 Pets

By NodeKey in ACM on

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 其实说白了 这个算法用途有限 只能求二分图的最大匹配（如果没有任何扩展，毕竟我是鶸…… 题目是一个人与狗的故事 这里每个人都想日狗 所以肯定是一对一的啊 但总共有 n个人 m只狗 e个先决条件 这些条件中 第ai个人不喜欢第bi只狗 问最多能让多少人 日到狗 AC Code #include #include #include #include #include #include #include using namespace std; const int inf=0x3f3f3f3f; const int maxn=1100; int n,m,qnum; int cus[maxn]; bool…