poj 1325 Machine Schedule(二分图的最小顶点覆盖，匈牙利算法)
poj 1325 题目链接 题意：有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组（i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启，问最少的重启次数。
思路：这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。
完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。
然后这道题就变成了二分图的最小顶点覆盖。
**二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最小点覆盖。**
根据Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。
一个证明：二分图最小顶点覆盖的证明
剩下的就是裸的hungary..
然而WA了好几次。。。
一个小细节没处理好。。。
由于初始是模式0.。。
所以模式0肯定要特殊考虑。。。因为初始状态是没有重启的。。。
但是我错误得以为只有当存在（i,0,0）这样的边时才忽略不算。。。
但是其实只要有一个端点是0就好了啊。。。不管哪端是0，我就用这个0来完成工作。。。依然不增加重启次数。。。
这不是什么坑点。。。脑袋秀逗了。。。
/* ***********************************************
Author :111qqz
Created Time :2016年05月26日 星期四 21时41分11秒
File Name :code/poj/1325.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E3+7;
7int n,m,k;
8int cnt;
9struct Edge
10{
11 int v;
12 int nxt;
13}edge[N];
1int head[N];
2int link[N];
3bool vis[N];
1void addedge( int u,int v)
2{
3 edge[cnt] .v = v;
4 edge[cnt].nxt = head[u];
5 head[u] = cnt;
6 cnt++;
7}
1bool dfs( int u)
2{
3 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
4 {
5 int v = edge[i].v;
6 if (vis[v]) continue;
7 vis[v] = true;
1 if (link[v]==-1||dfs(link[v]))
2 {
3 link[v] = u;
4 return true;
5 }
6 }
1 return false;
2}
3int hungary()
4{
5 int res = 0 ;
6 ms(link,-1);
1 for ( int i = 1 ; i <= n; i++)
2 {
3 ms(vis,false);
4 if (dfs(i)) res++;
5 }
6 return res;
7}
8int main()
9{
10 #ifndef ONLINE_JUDGE
11 freopen("code/in.txt","r",stdin);
12 #endif
13 while (scanf("%d",&n)!=EOF)
14 {
15 if (n==0) break;
16 scanf("%d %d",&m,&k);
17 ms(edge,0);
18 cnt = 0 ;
19 ms(head,-1);
20 int ans = 0 ;
21 for ( int i = 1 ; i <= k ; i++)
22 {
23 int id,u,v;
24 scanf("%d%d%d",&id,&u,&v);
25 if (u==0||v==0) continue ;//初始在0，那么只要边的一个端点是0，我们就可以选择在0完成，而不去重启。
26 u++;
27 v++;
1 v = v + n;
2 addedge(u,v);
3 }
1 ans = ans+hungary();
2 printf("%d\n",ans);
3 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}