Posts

hdu 3435题目链接 题意：给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值

hdu 1853 题目链接 题意：一个带权有向图，要求找出若干的环，满足每个点恰好在一个环里，并且环的权值和最小……问最小权值和。

hdu 2813 题目链接 题意：吕布有n个武将，曹操有m（m>=n）个武将。给出k个关系，为吕布的某个武将和曹操的某个武将pk后会受到的伤害。吕布要求他所有n的武将都要上场，每个武将只能战斗一次，问如何安排，使得所有武将受到的伤害总和最小。

hdu 2282 题目链接 题意：n个盒子围成一个圈，给出n个盒子中每个盒子中的巧克力个数，巧克力的总数不超过n，从一个盒子中移动一块巧克力到相邻的盒子里称为one “move”，（由于围成一个圈，所以第1个和第n个盒子也是相邻的） 问最小的移动“move”数，使得每个盒子里最多有一快巧克力。

hdu 3395题目链接 题意：鱼，一些鱼认为自己是汉子，然后他会去和他认为是妹子的鱼啪啪啪，然后被啪啪啪的妹子就会产卵？ 卵的val是它parent的val的异或。给出n，为鱼的数量，然后给出一个n*n的 mat,a[i][j]==1表示第i条鱼认为第j条鱼是妹子。问卵的最大val之和是多少。需要注意的是：每条鱼最多可以去和一个妹子啪，并且可以作为妹子被啪一次（这两个是独立的。。。） （Each fish can attack one other fish and can only be attacked once）

hdu 2426 题目链接 题意：n个学生，m个宿舍，每个学生住一个宿舍，然后n个学生给若干个宿舍打分，分数可正可0可负，学生不能住打的分为负的宿舍，或者没有打分的宿舍。问在满足上述条件的前提下，所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.

hdu 1533 题目链接 题意：给出一个n*m的maze，其中包含不超过一个人（用m表示），以及和人数相等的房子（用H表示），其他都是‘.’，表示可以经过的路径。人向一个方向移动花费代价1.问每个人都回到一个房子里的最小代价是多少。ps:每个格子是无限大的，也就是所有人可以同时踩在一个格子里。以及：路过一个房子可以不住，而只是“经过”。

hdu 2255 题目链接 题意：传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。 这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。 另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).

poj 3041题目链接 题意：一个nn的网格中，有k个大小为11的小行星，现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。

poj1719题目链接 题意：射箭比赛，靶子是一个n*m的网格。网格的特点是没列只有两个白色，剩下的全是黑色。一共射m次，每列射一次，要求每行都射到至少一次才算合法，问是否有合法射法，如果有输出一组解。

hdu 4185题目链接 题意：给出一个nn的字符maze,‘.’代表水，‘#’代表油田。 挖油的机器一次会挖两个相邻方块。要求是必须两块必须都是油，不然会有杂质。问最多能挖多少次。 思路：和那道用12的小矩形块填充是一个思路。根据奇偶性对点标号，然后建图，匈牙利，2A. 第一遍是dfs写错了一个变量QAQ.a

hdu 1068题目链接 题意：有n个同学。。给出同学之间的 爱慕关系。。。选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。

hdu 3225题目链接 题意：给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行，并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案，那么输出-1.

poj 1469 题目链接 题意：p个课程，n个学生，给出每个课程对应选取该课程的学生编号，问能否选出p个学生，使得和课程一一对应。

poj 1325 题目链接 题意：有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组（i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启，问最少的重启次数。

poj 1422题目链接 题意+思路：DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。

poj 2594 题目链接 题意：一个DAG图，每个点有宝藏…可以降落任意个机器人到任意点…然后机器人可以沿着路径走，路过某个点的时候，可以取走该点的宝藏。问要取走所有宝藏，最少需要多少个机器人。

poj 2446 题目链接 题意：一个nm的矩形方格里，有k个坏点，然后问能否用12的矩形块将矩形方格填满。坏点不能填，小的矩形块不能重叠，不能超出边界。不能有好点没有被填。

poj 1274题目链接 裸的匈牙利。 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月25日 星期三 17时49分22秒 4File Name :code/poj/1274.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=405; 34int n,m; 35int head[N]; 36int cnt; 37int link[N]; 38bool vis[N]; 39struct Edge 40{ 41 int v; 42 int nxt; 43}edge[N*N]; 44void addedge(int u,int v) 45{ 46 edge[cnt].v = v; 47 edge[cnt].nxt = head[u]; 48 head[u] = cnt; 49 cnt++; 50} 51 52bool dfs( int u) 53{ 54 // cout<<"u:"<<u<<endl; 55 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt) 56 { 57 int v = edge[i].v; 58// cout<<"v:"<<v<<endl; 59 if (vis[v]) continue; 60 vis[v] = true; 61 62 if (link[v]==-1||dfs(link[v])) 63 { 64 link[v] = u; 65 return true; 66 } 67 } 68 return false; 69} 70int hung() 71{ 72 int res = 0 ; 73 ms(link,-1); 74 for ( int i = 1 ; i <= n ; i++) 75 { 76 ms(vis,false); 77 if (dfs(i)) res++; 78 } 79 80 return res; 81} 82int main() 83{ 84 #ifndef ONLINE_JUDGE 85 freopen("code/in.txt","r",stdin); 86 #endif 87 88 while (scanf("%d%d",&n,&m)!=EOF) 89 { 90 ms(head,-1); 91 cnt = 0 ; 92 93 for ( int i = 1 ; i <= n ; i++) 94 { 95 int num; 96 scanf("%d",&num); 97 while (num--) 98 { 99 int x; 100 scanf("%d",&x); 101 x = x + n; 102 addedge(i,x); 103 } 104 } 105 int ans = hung(); 106 printf("%d\n",ans); 107 } 108 109 #ifndef ONLINE_JUDGE 110 fclose(stdin); 111 #endif 112 return 0; 113}

hdu2063题目链接 题意：求二分图最大匹配。 思路：匈牙利算法。 通过这三篇博客了解了相关概念，学习了匈牙利算法。 趣写算法系列之–匈牙利算法 二分图的最大匹配、完美匹配和匈牙利算法 匈牙利算法详解