在网上搜的二分图模板题。
题意: A、B两个机器各自有不同的工作模式,给出一个工作序列,每项工作,A、B在各自的某种特定模式下可以完成。但是,机器开始的时候模式都为0,换模式,需要一次restart,要求总共的restart次数最少是多少。
类型:二分图最大匹配 / 最小点覆盖 / 匈牙利
分析:虽然知道是二分图的题,但是由于对最小点覆盖不敏感,看了简单的输入后觉得可以用贪心模拟做。后来还是发现不行,考虑以下两点理由:
1、各种工作是可以不按输入的顺序去完成的(这个题目貌似没说清楚是吧?)
2、这是一个匹配问题!
反思:以后对最小点覆盖肯定更敏感了,第一时间找出模型。
代码:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define MAXN 102 //点标号 0、1~n-1 n、n+1~n+m-1 #define MAXK 1002 int G[MAXN][MAXN+MAXN]; int n, m, k; //n: X集合 m:Y集合 k:边数 int vis[MAXN+MAXN], flag[MAXN+MAXN]; int dfs(int u) { for(int v=n+1; v<n+m; v++) if(G[u][v]) { if(!vis[v]) { vis[v] = 1; if(!flag[v] || dfs(flag[v])) { flag[v] = u; //取反 return 1; } } } return 0; } int read_graph() { memset(G, 0, sizeof(G)); cin>>n>>m>>k; if(!n) return 0; for(int i=0; i<k; i++) { int junk, u, v; cin>>junk>>u>>v; if(!u || !v) continue; //若其中一个为0,不加边 G[u][v+n] = 1; // G[v+n][u] = 1; //只需要在X-》Y 间连线 } return 1; } int main() { while(read_graph()) { int cnt = 0; memset(flag, 0, sizeof(flag)); for(int i=1; i<n; i++) { memset(vis, 0, sizeof(vis)); if(dfs(i)) { cnt++; } } cout<<cnt<<endl; } }