本文主要是介绍HDU 3861 The King’s Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
The King’s Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1828 Accepted Submission(s): 664
Now the king asks for your help, he wants to know the least number of states he have to divide the kingdom into.
The first line for each case contains two integers n, m(0 < n <= 5000,0 <= m <= 100000), the number of cities and roads in the kingdom. The next m lines each contains two integers u and v (1 <= u, v <= n), indicating that there is a road going from city u to city v.
1 3 2 1 2 1 3
2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 5000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
vector<int>G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int>S;
int n;
void dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!sccno[v])lowlink[u]=min(lowlink[u],pre[v]);
}
if(lowlink[u]==pre[u])
{
scc_cnt++;
for(;;)
{
int x=S.top();S.pop();
sccno[x]=scc_cnt;
if(x==u)break;
}
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
cle(sccno),cle(pre);
for(int i=1;i<=n;i++)
if(!pre[i])dfs(i);
}
vector<int>g[maxn];
int match[maxn];
int vis[maxn];
int tot;
int dfs2(int x)
{
for(int i=0;i<g[x].size();i++)
if(!vis[g[x][i]])
{
vis[g[x][i]]=1;
if(match[g[x][i]]==-1||dfs2(match[g[x][i]]))
{
match[g[x][i]]=x;
return 1;
}
}
return 0;
}
int hungary()
{
tot=0;
memset(match,-1,sizeof match);
for(int i=1;i<=n;i++)
{
cle(vis);
if(dfs2(i))tot++;
}
return scc_cnt-tot;
}
void solve()
{
find_scc(n);
for(int i=1;i<maxn;i++)
g[i].clear();
//用scc构建图
for(int i=1;i<=n;i++)
for(int j=0;j<G[i].size();j++)
{
int k=G[i][j];
if(sccno[i]==sccno[k])continue;
g[sccno[i]].push_back(sccno[k]);
}
printf("%d\n",hungary());
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int m,t;
int a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<maxn;i++)
G[i].clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
solve();
}
return 0;
}
这篇关于HDU 3861 The King’s Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
