很明显是最小路径覆盖,只是必须先要求传递闭包就行了。
- #include <stdio.h>
- #include <string.h>
- #define N 510
- int uN,vN;
- int g[N][N];
- int linker[N];
- bool used[N];
- bool DFS(int u)
- {
- int v;
- for(v=0;v<vN;v++)
- {
- if(g[u][v]&&!used[v])
- {
- used[v]=true;
- if(linker[v]==-1||DFS(linker[v]))
- {
- linker[v]=u;
- return true;
- }
- }
- }
- return false;
- }
- int Hungary()
- {
- int u;
- int ret=0;
- memset(linker,-1,sizeof(linker));
- for(u=0;u<uN;u++)
- {
- memset(used,false,sizeof(used));
- if(DFS(u)) ret++;
- }
- return ret;
- }
- void Floyd(int n)
- {
- int i,j,k;
- for(i=0;i<n;i++)
- {
- for(j=0;j<n;j++)
- {
- if(g[i][j]==0)
- {
- for(k=0;k<n;k++)
- {
- if(g[i][k]==1&&g[k][j]==1)
- {
- g[i][j]=1;
- break;
- }
- }
- }
- }
- }
- }
- int main()
- {
- int n,m;
- int u,v;
- while(~scanf("%d%d",&n,&m))
- {
- if(n==0&&m==0) break;
- uN=vN=n;
- memset(g,0,sizeof(g));
- while(m--)
- {
- scanf("%d%d",&u,&v);
- u--;v--;
- g[u][v]=1;
- }
- Floyd(n);
- int ans=Hungary();
- printf("%d\n",n-ans);
- }
- return 0;
- }