匈牙利算法

1059: [ZJOI2007]矩阵游戏 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5251 Solved: 2512 [Submit][Status][Discuss] Description # 小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）；列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）。游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。

1191: [HNOI2006]超级英雄Hero # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5221 Solved: 2356 [Submit][Status][Discuss] Description # 现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？

hdu 2444题目链接 题意：判断一个有向图是否是二分图，是的话求最大匹配数。 思路：交叉染色判二分图，是的话跑遍匈牙利即可。1A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年09月01日 星期四 14时24分36秒 4File Name :code/hdu/2444.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=205; 32int n,m; 33vector<int>edge[N]; 34int col[N]; 35int link[N]; 36bool vis[N]; 37void init() 38{ 39 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 40 ms(col,-1); 41} 42bool dfs( int u,int x) 43{ 44 col[u] = x; 45 int siz = edge[u].size(); 46 for ( int i = 0 ; i < siz; i++) 47 { 48 int v = edge[u][i]; 49 if (col[v]==1-x) continue; 50 if (col[v]==x) return false; 51 if (!dfs(v,1-x)) return false; 52 } 53 return true; 54} 55bool solve() 56{ 57 for ( int i = 1 ; i <= n ; i++) if (col[i]==-1) if (!dfs(i,0)) return false; 58 return true; 59} 60bool Find( int u) 61{ 62 int siz = edge[u].size(); 63 for ( int i = 0 ; i < siz; i ++) 64 { 65 int v = edge[u][i]; 66 if (vis[v]) continue; 67 vis[v] = true; 68 if (link[v]==-1||Find(link[v])) 69 { 70 link[v] = u; 71 return true; 72 } 73 } 74 return false; 75} 76int hung( int n) 77{ 78 int ans = 0 ; 79 ms(link,-1); 80 for ( int i = 1 ; i <= n ; i++) 81 { 82 ms(vis,false); 83 if (Find(i)) ans++; 84 } 85 return ans; 86} 87int main() 88{ 89 #ifndef ONLINE_JUDGE 90 freopen("code/in.txt","r",stdin); 91 #endif 92 while (~scanf("%d %d",&n,&m)) 93 { 94 init(); 95 for ( int i = 1 ; i <= m ; i++) 96 { 97 int u,v; 98 scanf("%d%d",&u,&v); 99 edge[u].push_back(v); 100 } 101 if (!solve()) 102 { 103 puts("No"); 104 } 105 else 106 { 107 int ans = hung(n); 108 printf("%d\n",ans); 109 } 110 } 111 #ifndef ONLINE_JUDGE 112 fclose(stdin); 113 #endif 114 return 0; 115}

学完了km..感觉匈牙利真是非常的。。easy… 匈牙利算法学习链接 有一种题目会用1*2的小格子填充大的，问能不能填满之类的，可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告

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个学生，使得和课程一一对应。 思路：一眼二分图最大匹配。。。需要注意的是。。两个集合可能分别给出。。建图的最大点数是两个集合的最大数目之和。。。因为没注意这个细节RE了一次。。

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

poj 1422题目链接 题意+思路：DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月26日 星期四 20时24分15秒 4File Name :code/poj/r2594.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=505; 34int n,m; 35bool conc[N][N]; 36bool vis[N]; 37int link[N]; 38void floyd() 39{ 40 for ( int k = 1 ; k <= n ; k++) 41 for ( int i = 1 ; i <= n ; i++) 42 for ( int j = 1 ; j <= n ; j++) 43 if (conc[i][k]&&conc[k][j]) conc[i][j] = true; 44} 45 46 47bool dfs( int u) 48{ 49 for ( int i = 1 ; i <= n ; i++) 50 { 51 if (conc[u][i]) 52 { 53 if (vis[i]) continue; 54 vis[i] = true; 55 if (link[i]==-1||dfs(link[i])) 56 { 57 link[i] = u; 58 return true; 59 } 60 } 61 } 62 return false; 63} 64int hungary() 65{ 66 int res = 0 ; 67 ms(link,-1); 68 for ( int i = 1 ; i <= n ; i++) 69 { 70 ms(vis,false); 71 if (dfs(i)) res++; 72 } 73 return res; 74} 75int main() 76{ 77 #ifndef ONLINE_JUDGE 78 freopen("code/in.txt","r",stdin); 79 #endif 80 81 while (scanf("%d%d",&n,&m)!=EOF) 82 { 83 if (n==0&&m==0) break; 84 ms(conc,false); 85 for ( int i = 1 ; i <= m ; i++) 86 { 87 int u,v; 88 scanf("%d%d",&u,&v); 89 conc[u][v] = true; 90 } 91 92 floyd(); 93 int ans = hungary(); 94 printf("%d\n",n-ans); 95 96 } 97 98 #ifndef ONLINE_JUDGE 99 fclose(stdin); 100 #endif 101 return 0; 102}

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

poj 2446 题目链接 题意：一个 nm 的矩形方格里，有 k 个坏点，然后问能否用 12 的矩形块将矩形方格填满。坏点不能填，小的矩形块不能重叠，不能超出边界。不能有好点没有被填。 思路：乍一看没什么好的思路。然后发现小的矩形块只能有两种放置方法（横着放，竖着放）。可能我们对于第 i 个，可以横着放，也可以竖着放，但是可能某种方案使得后面的某一块没办法放置，因此我们需要反过来调整第 i 块的放法。这个过程似乎和二分图匹配有点类似？那到底有没有相似点呢，又如何划分集合呢？

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题目链接 题意：求二分图最大匹配。 思路：匈牙利算法。 通过这三篇博客了解了相关概念，学习了匈牙利算法。 趣写算法系列之–匈牙利算法 二分图的最大匹配、完美匹配和匈牙利算法 匈牙利算法详解 感受就是：这个是相对容易学的算法。。并没有名字那么不明觉厉。。。 主体就是一个dfs的过程。。。。