本文主要是介绍hdu3861 The King’s Problem --- 强连通+二分图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给一个n个点的有向图，要把n个点分成尽量少的部分，使每个部分里的任意两点间两两可达，而且强连通分量必须在一个部分里。
缩点后建新图，二分图最小路径覆盖。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll long long
using namespace std;
#define M 5010//图中点数
int sta[M],top;
bool vis[M];
int dfn[M];
int low[M];
int ccnt; //有向图强连通分量个数
int id;
vector<int> e[M];//原图
vector<int> edge[M];//新图
vector<int> part[M];//每个联通块的组成
int inpart[M];//每个原图上的点在哪个联通块里
int n,m;void tarjan(int x)
{int i,j;dfn[x]=low[x]=id++;vis[x]=1;sta[++top]=x;for(i=0;i<e[x].size();i++){j=e[x][i];if(dfn[j]==-1){tarjan(j);low[x]=min(low[x],low[j]);}else if(vis[j])low[x]=min(low[x],dfn[j]);}if(dfn[x]==low[x]){do{j=sta[top--];vis[j]=0;part[ccnt].push_back(j);inpart[j]=ccnt;}while(j!=x);ccnt++;}
}void solve(int n)
{memset(sta,-1,sizeof sta);memset(vis,0,sizeof vis);memset(dfn,-1,sizeof(dfn));memset(low,-1,sizeof(low));top=ccnt=id=0;for(int i=1;i<=n;i++)if(dfn[i]==-1)tarjan(i);
}int mx[M],my[M];int path(int u)
{int i,v;for(i=0;i<edge[u].size();i++){v=edge[u][i];if(!vis[v]){vis[v]=1;if(my[v]==-1||path(my[v])){mx[u]=v;my[v]=u;return 1;}}}return 0;
}int hungary()
{int res=0;memset(mx,-1,sizeof mx);memset(my,-1,sizeof my);for(int i=0;i<ccnt;i++){if(mx[i]==-1){memset(vis,0,sizeof vis);res+=path(i);}}return res;
}int main()
{int icy,a,b,i,j;scanf("%d",&icy);while(icy--){scanf("%d%d",&n,&m);for(i=0;i<=n;i++){part[i].clear();e[i].clear();edge[i].clear();}while(m--){scanf("%d%d",&a,&b);e[a].push_back(b);}solve(n);for(i=1;i<=n;i++){for(j=0;j<e[i].size();j++){int a=inpart[i];int b=inpart[e[i][j]];if(a!=b)edge[a].push_back(b);}}int ans=hungary();printf("%d\n",ccnt-ans);}return 0;
}
这篇关于hdu3861 The King’s Problem --- 强连通+二分图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
