ACM

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

uva10986题目链接 题意：裸的spfa. 思路：模板，1A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月25日 星期三 03时25分27秒 4File Name :code/uva/10986.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=2E4+7; 34int n,m; 35int S,T; 36vector < pi > edge[N]; 37 38int d[N]; 39bool inq[N]; 40bool spfa( int s,int t) 41{ 42 ms(d,0x3f); 43 ms(inq,false); 44 queue<int>q; 45 q.push(s); 46 inq[s] = true; 47 d[s] = 0; 48 49 while (!q.empty()) 50 { 51 int u = q.front(); 52 q.pop(); 53 inq[u] = false; 54 55 int siz = edge[u].size(); 56 57 for ( int i = 0 ; i < siz ; i++) 58 { 59 int v = edge[u][i].fst; 60 if (d[v]>d[u] + edge[u][i].sec) 61 { 62 d[v] = d[u] + edge[u][i].sec; 63 if (inq[v]) continue; 64 inq[v] = true; 65 q.push(v); 66 } 67 } 68 } 69 return d[t]!=inf; 70} 71int main() 72{ 73 #ifndef ONLINE_JUDGE 74 freopen("code/in.txt","r",stdin); 75 #endif 76 ios::sync_with_stdio(false); 77 int TT; 78 cin>>TT; 79 int cas = 0 ; 80 while (TT--) 81 { 82 cin>>n>>m>>S>>T; 83 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 84 for ( int i = 1 ; i <= m ; i++) 85 { 86 int u,v,w; 87 cin>>u>>v>>w; 88 edge[u].push_back(make_pair(v,w)); 89 edge[v].push_back(make_pair(u,w)); 90 } 91 92 if (spfa(S,T)) 93 { 94 printf("Case #%d: %d\n",++cas,d[T]); 95 } 96 else 97 { 98 printf("Case #%d: unreachable\n",++cas); 99 } 100 101 } 102 103 #ifndef ONLINE_JUDGE 104 fclose(stdin); 105 #endif 106 return 0; 107}

poj2949 题目链接 题意：我们有 n 个 (n<=100000) 字符串，每个字符串都是由 a~z 的小写英文字母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相接形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最长。

poj 1860 题目链接 题意：有n种货币，m个货币交易点，每个货币交易点只能是两种货币之间交换，给出两个方向的汇率和手续费。初始拥有数量v的货币s，问能否经过一些py交易，使得最后手里的货币s比v多。

poj1932题目链接 题意：初始在点 1，有 100 点能量，然后每个点有一个能量值【-100,100】，经过某个点会加上这个点的能量值，问能否找到一条到点 n 的路线，且路径上任何点的能量值一直为正。一共不超过 100 个点。

poj 1511 题目链接 题意：和那道奶牛的舞会类似，要求所有点到点1的距离和加上1点到所有点的距离和。 思路：正反存边建两次图，跑两次spfa. 然而用vector会TLE….所以去学习了新的建图方式。。。也就是链式前向星：链式前向星（边表）学习链接 也叫边表。

1614: [Usaco2007 Jan]Telephone Lines架设电话线 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1325 Solved: 570 [Submit][Status][Discuss] Description # Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。