bzoj 1143 [CTSC2008]祭祀river（最小链覆盖）

本文主要是介绍bzoj 1143 [CTSC2008]祭祀river（最小链覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1143

在南宁被这个题无限关。。。

将每个点分成两个集合X和Y，如果a到b有一条路径，就添加一条aX到bY的边，然后跑出最大匹配，然后n-最大匹配数就是最小链覆盖。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=110;
int n,m;
bool used[MAXN],g[MAXN][MAXN];//邻接矩阵 
int linker[MAXN];
bool dfs(int u)
{for(int v=1;v<=n;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 res=0; memset(linker,-1,sizeof(linker));for(int u=1;u<=n;u++){memset(used,false,sizeof(used));if(dfs(u))res++;}return res;
}
void solve()
{memset(g,false,sizeof(g));for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);g[u][v]=true;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]|=g[i][k]&g[k][j];}}}printf("%d\n",n-hungary());
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(~scanf("%d%d",&n,&m)){solve();}return 0;
}

这篇关于bzoj 1143 [CTSC2008]祭祀river（最小链覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---