Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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来完成工作。。。依然不增加重启次数。。。
这不是什么坑点。。。脑袋秀逗了。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月26日 星期四 21时41分11秒
4File Name :code/poj/1325.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=1E3+7;
34int n,m,k;
35int cnt;
36struct Edge
37{
38 int v;
39 int nxt;
40}edge[N];
41
42
43int head[N];
44int link[N];
45bool vis[N];
46
47void addedge( int u,int v)
48{
49 edge[cnt] .v = v;
50 edge[cnt].nxt = head[u];
51 head[u] = cnt;
52 cnt++;
53}
54
55
56bool dfs( int u)
57{
58 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
59 {
60 int v = edge[i].v;
61 if (vis[v]) continue;
62 vis[v] = true;
63
64 if (link[v]==-1||dfs(link[v]))
65 {
66 link[v] = u;
67 return true;
68 }
69 }
70
71 return false;
72}
73int hungary()
74{
75 int res = 0 ;
76 ms(link,-1);
77
78 for ( int i = 1 ; i <= n; i++)
79 {
80 ms(vis,false);
81 if (dfs(i)) res++;
82 }
83 return res;
84}
85int main()
86{
87 #ifndef ONLINE_JUDGE
88 freopen("code/in.txt","r",stdin);
89 #endif
90 while (scanf("%d",&n)!=EOF)
91 {
92 if (n==0) break;
93 scanf("%d %d",&m,&k);
94 ms(edge,0);
95 cnt = 0 ;
96 ms(head,-1);
97 int ans = 0 ;
98 for ( int i = 1 ; i <= k ; i++)
99 {
100 int id,u,v;
101 scanf("%d%d%d",&id,&u,&v);
102 if (u==0||v==0) continue ;//初始在0，那么只要边的一个端点是0，我们就可以选择在0完成，而不去重启。
103 u++;
104 v++;
105
106 v = v + n;
107 addedge(u,v);
108 }
109
110 ans = ans+hungary();
111 printf("%d\n",ans);
112 }
113
114 #ifndef ONLINE_JUDGE
115 fclose(stdin);
116 #endif
117 return 0;
118}