大意:有两台机器A和B。机器A有n中工作模式,B有m种工作模式。给定k个作业,每换一个模式需要重启一次,让你求出完成k个作业机器最小的重启次数。机器A和B的初始模式为0。
思路:任务i在A的mode_x与B的mode_y都可以做的话,那么就连一条边。这样问题就转换成了边最小覆盖的问题,而最小覆盖又可以通过最大匹配来求解。
在写邻接表时要注意一个问题,就是在模式0完成的工作不需要重启,因此可以用 u*v的大小来判断是否连边。
邻接表:
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 110; const int MAXM = 1010; struct Edge { int v, next; }edge[MAXM]; int first[MAXN], link[MAXN]; bool vis[MAXN]; int n, m, k; int cnt; inline void init() { cnt = 0; memset(first, -1, sizeof(first)); memset(link, -1, sizeof(link)); } inline void read_graph(int u, int v) { edge[cnt].v = v; edge[cnt].next = first[u], first[u] = cnt++; } inline int read_graph2() { init(); scanf("%d", &n); if(!n) return false; scanf("%d%d", &m, &k); while(k--) { int job, u, v; scanf("%d%d%d", &job, &u, &v); if(u * v) { read_graph(u, v); } } return true; } bool ED(int u) { for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v; if(!vis[v]) { vis[v] = 1; if(link[v] == -1 || ED(link[v])) { link[v] = u; return true; } } } return false; } void solve() { int ans = 0; for(int i = 0; i <= n; i++) //从0开始的 { memset(vis, 0, sizeof(vis)); if(ED(i)) ans++; } printf("%d\n", ans); } int main() { while(read_graph2()) { solve(); } return 0; }
我们也可以通过邻接矩阵来写,我们循环是直接从1开始,而不是从0,这样我们就避免了重复计算的问题。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAXN 110 #define MAXM 10010 int G[MAXN][MAXN]; int first[MAXN]; int xlink[MAXN], ylink[MAXN]; bool visy[MAXN]; int nx, ny, jobnum; void init() { memset(G, 0, sizeof(G)); memset(xlink, -1, sizeof(xlink)); memset(ylink, -1, sizeof(ylink)); } bool ED(int u) { for(int v = 1; v <= ny; v++) if(G[u][v]) //本来应该从0开始循环,但考虑所有在Yi中的顶点,由于A、B最初工作模式为0,所以不需要重启机器。 { if(!visy[v]) { visy[v] = 1; if(ylink[v] == -1 || ED(ylink[v])) { xlink[u] = v; ylink[v] = u; return true; } } } return false; } void solve() { int ans = 0; for(int i = 1; i <= nx; i++) //同上 { if(xlink[i] == -1) { memset(visy, 0, sizeof(visy)); ans += ED(i); } } printf("%d\n", ans); } inline void read_graph2() { scanf("%d%d", &ny, &jobnum); while(jobnum--) { int job, u, v; scanf("%d%d%d", &job, &u, &v); G[u][v] = 1; } } int main() { while(scanf("%d", &nx) && nx) { init(); read_graph2(); solve(); } return 0; }