poj2594 Treasure Exploration 最小路径覆盖=顶点数-最大匹配数

这道题走过的点可以重复走，这样不符合二分匹配，可是我们可以转化，最简单的就是使用floyd，比如说 1->2->3，2号点已经走过了，我们可以赋予从1->3可以直接到，不需要经过2号点就可以了，这样2号点就不会出现被重复覆盖的现象，那我们就使用floyd来解决问题，剩下的就是套模版的问题了

#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;vector<int>G[1212];char tempmp[1212][1212];int mp[1212][1212];int marry[1212];bool vis[1212];int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m;void clear(){memset(marry,-1,sizeof(marry));memset(mp,0,sizeof(mp));for(int i=0;i<1012;i++)G[i].clear();}void floyd(){for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j && mp[i][k] && mp[k][j])//如果i可以到k，k可以到j，那么i可以直接到j，mp[i][j]=1;}bool dfs(int x){for(int i=0;i<n;i++){if(mp[x][i] && !vis[i]){vis[i]=true;if(marry[i]==-1 || dfs(marry[i])){marry[i]=x;return 1;}}}return 0;}int main(void){while(scanf("%d %d",&n,&m),n+m){clear();int u,v;/*for(int i=0;i<n;i++)mp[i][i]=1;*/for(int i=0;i<m;i++){cin>>u>>v;u--;v--;mp[u][v]=1;}floyd();int ans=0;for(int i=0;i<n;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}ans=n-ans;//最小路径覆盖=顶点数-最大匹配数（看情况是否要除2，因为无向的就要除2，有向的二分匹配图就不需要）if(ans==0)puts("1");elsecout<<ans<<endl;}}