大意不再赘述。
思路:一看我就知道是最小路径覆盖,但题目给出的条件是可以一条路径可以覆盖一个点很多次,如果单纯的求二分最大匹配,可能会遗漏一些情况。我也不会写,想了2、3天,去看看DISCUSS后,说要用到传递闭包,然后我就思考为什么要这样,想了很久,不是很懂,但还是有一点感觉了。其实就是匹配的时候,由于某些边可能占据了一些交点啥的,然后通过传递闭包,我们可以“绕过”那个交点,然后再进行匹配,这不影响结果,但却可以用经典的二分图模型去求解了,题目模型的抽象与理解才是重点啊。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; const int MAXN = 510; const int MAXM = 5010; int G[MAXN][MAXN]; int xlink[MAXN], ylink[MAXN]; bool vis[MAXN]; int nx, ny, m; inline void init() { memset(G, 0, sizeof(G)); memset(xlink, -1, sizeof(xlink)); memset(ylink, -1, sizeof(ylink)); } void Floyd() { for(int k = 1; k <= nx; k++) for(int i = 1; i <= nx; i++) for(int j = 1; j <= nx; j++) G[i][j] = G[i][j] || (G[i][k] && G[k][j]); } //这里需要用到传递闭包的原因是因为一旦匹配后,为了“绕过”已匹配的边,所以需要把所有的传递性都连接起来。 bool ED(int u) { for(int v = 1; v <= ny; v++) if(G[u][v]) { if(!vis[v]) { vis[v] = 1; if(ylink[v] == -1 || ED(ylink[v])) { xlink[u] = v; ylink[v] = u; return true; } } } return false; } inline int read_case() { init(); scanf("%d%d", &nx, &m); ny = nx; if(!nx && !ny) return 0; while(m--) { int u, v; scanf("%d%d", &u, &v); G[u][v] = 1; } return 1; } void solve() { int ans = 0; Floyd(); for(int i = 1; i <= nx; i++) if(xlink[i] == -1) { memset(vis, 0, sizeof(vis)); ans += ED(i); } printf("%d\n", nx-ans); } int main() { while(read_case()) { solve(); } return 0; }