有n个城市和m条有向通道。如果从某个城市一条道路一直走到没有路可走，那么在这条首路上的所有城市划分成一个国家，每个城市只能属于一个国家，一个环形上的城市当然也是属于同一国家。问这些城市最少分为多少个国家。
因为有向图中存在环，而二分图是在有向无环图时才正确，所以先用强连通缩点重新构成有向无环图。再二分匹配。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;
const int N=10005;
vector<int> g[N];
stack<int> q;
int n,m,dfs_clock,scc_cnt;
int dfn[N],low[N],sccno[N],link[N];
bool vis[N],map[N][N];
void Init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(sccno,0,sizeof(sccno));
memset(map,false,sizeof(map));
dfs_clock=scc_cnt=0;
for(int i=0;i<=n;i++)
g[i].clear();
while(!q.empty())
q.pop();
}
void tarjan(int u)
{
dfn[u]=low[u]=++dfs_clock;
q.push(u);
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!sccno[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scc_cnt++;
while(!q.empty())
{
int v=q.top();
q.pop();
sccno[v]=scc_cnt;
if(v==u)
break;
}
}
}
bool dfs(int u)
{
for(int i=1;i<=n;i++)
{
if(!vis[i]&&map[u][i])
{
vis[i]=true;
if(!link[i]||dfs(link[i]))
{
link[i]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int ans=0;
memset(link,0,sizeof(link));
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i))
ans++;
}
return scc_cnt-ans;
}
int main()
{
int t,u,v;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
Init();
while(m--)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int u=1;u<=n;u++)
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(sccno[u]!=sccno[v])
map[sccno[u]][sccno[v]]=1;
}
printf("%d\n",hungary());
}
return 0;
}
明志留
发布了44 篇原创文章 · 获赞 35 · 访问量 778
私信
关注