我又回来了!!!!
这是典型的求最小可相交路径覆盖
我们先求闭包,利用闭包连边,然后求解最小不可相交路径就可以了。
什么?如何求解最小不可相交路径覆盖?
点数-最大匹配数
代码如下:
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int max_n = 550; const int inf = 2e9; struct edge{ int to,next; }E[max_n*max_n*max_n]; int head[max_n]; int cnt=1; void add(int from,int to){ E[cnt].to=to;E[cnt].next = head[from]; head[from]=cnt++; } int leftTo[max_n], rightTo[max_n]; int distleft[max_n], distright[max_n]; int dist; bool seacherpath(int left_tot, int right_tot) { fill(distleft, distleft + left_tot + 1, -1); fill(distright, distright + right_tot + 1, -1); queue<int> que;dist = inf; for (int i = 1;i <= left_tot;++i) if (leftTo[i] == -1) que.push(i); while (!que.empty()) { int u = que.front();que.pop(); if (distleft[u] > dist)break; for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (distright[v] != -1)continue; distright[v] = distleft[u] + 1; if (rightTo[v] == -1)dist = distright[v]; else { distleft[rightTo[v]] = distright[v] + 1; que.push(rightTo[v]); } } }return dist != inf; } bool matchpath(int u) { for (int i = head[u];i;i = E[i].next) { int v = E[i].to; if (distright[v] != distleft[u] + 1)continue; if (distright[v] == dist && rightTo[v] != -1)continue; distright[v] = -1; if (rightTo[v] == -1 || matchpath(rightTo[v])) { leftTo[u] = v; rightTo[v] = u; return true; } }return false; } int HK(int left_tot, int right_tot) { fill(leftTo, leftTo + left_tot + 1, -1); fill(rightTo, rightTo + right_tot + 1, -1); int ans = 0; while (seacherpath(left_tot, right_tot)) { for (int i = 1;i <= left_tot;++i) if (leftTo[i] == -1 && matchpath(i)) ++ans; }return ans; } bool tr[550][550]; int main(){ int n,m; while(scanf("%d %d",&n,&m)){ if (n==m&&n==0)break; fill(head,head+n+5,0); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) tr[i][j]=0; cnt=1; for (int i=1,u,v;i<=m;++i){ scanf("%d %d",&u,&v); tr[u][v]=1; } for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) tr[i][j]=tr[i][k]&tr[k][j]|tr[i][j]; for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) if (tr[i][j]) add(i,j); printf("%d\n",n-HK(n,n)); } }