The King’s Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2947 Accepted Submission(s): 1049
the Kingdom of Silence, the king has a new problem. There are N cities
in the kingdom and there are M directional roads between the cities.
That means that if there is a road from u to v, you can only go from
city u to city v, but can’t go from city v to city u. In order to rule
his kingdom more effectively, the king want to divide his kingdom into
several states, and each city must belong to exactly one state. What’s
more, for each pair of city (u, v), if there is one way to go from u to
v and go from v to u, (u, v) have to belong to a same state. And
the king must insure that in each state we can ether go from u to v or
go from v to u between every pair of cities (u, v) without passing any
city which belongs to other state.
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.
output should contain T lines. For each test case you should just
output an integer which is the least number of states the king have to
divide into.
转载一篇苣苣的博客:有向无环图(DAG)的最小路径覆盖
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e4+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e13+;
struct edge
{
int from,to;
int cost;
};
edge es[maxm];
priority_queue<P,vector<P>,greater<P> >que;
vector<int>G[maxn],T[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int>s;
void dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
s.push(u);
for(int i=; 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++;
while(true)
{
int x=s.top();
s.pop();
sccno[x]=scc_cnt;
if(x==u) break;
}
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=;
memset(sccno,,sizeof(sccno));
memset(pre,,sizeof(pre));
for(int i=; i<=n; i++)
if(!pre[i]) dfs(i);
}
void build(int m)
{
for(int i=; i<=scc_cnt; i++) T[i].clear();
for(int i=; i<=m; i++)
{
int u=es[i].from,v=es[i].to;
if(sccno[u]==sccno[v]) continue;
T[sccno[u]].push_back(sccno[v]);
}
}
int cy[maxn],vis[maxn];
bool dfs2(int u)
{
for(int i=; i<T[u].size(); i++)
{
int v=T[u][i];
if(vis[v]) continue;
vis[v]=true;
if(cy[v]==-||dfs2(cy[v]))
{
cy[v]=u;
return true;
}
}
return false;
}
int solve(int n)
{
int ret=;
memset(cy,-,sizeof(cy));
for(int i=; i<=n; i++)
{
memset(vis,,sizeof(vis));
ret+=dfs2(i);
}
return n-ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) G[i].clear();
for(int i=; i<=m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
es[i].from=u,es[i].to=v;
G[u].push_back(v);
}
find_scc(n);
build(m);
cout<<solve(scc_cnt)<<endl;
}
return ;
}
tarjan缩点+最小路径覆盖
HDU 3861.The King’s Problem 强联通分量+最小路径覆盖的更多相关文章
-
HDU 3861 The King’s Problem(强连通分量+最小路径覆盖)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3861 题目大意: 在csdn王国里面, 国王有一个新的问题. 这里有N个城市M条单行路,为了让他的王国 ...
-
HDU 3861 The King’s Problem(强连通+二分图最小路径覆盖)
HDU 3861 The King's Problem 题目链接 题意:给定一个有向图,求最少划分成几个部分满足以下条件 互相可达的点必须分到一个集合 一个对点(u, v)必须至少有u可达v或者v可达 ...
-
HDU 3861 The King&#39;s Problem(强连通分量缩点+最小路径覆盖)
http://acm.hdu.edu.cn/showproblem.php?pid=3861 题意: 国王要对n个城市进行规划,将这些城市分成若干个城市,强连通的城市必须处于一个州,另外一个州内的任意 ...
-
hdu 3861 The King’s Problem trajan缩点+二分图匹配
The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other ...
-
HDU 3861 The King’s Problem 最小路径覆盖(强连通分量缩点+二分图最大匹配)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3861 最小路径覆盖的一篇博客:https://blog.csdn.net/qq_39627843/ar ...
-
hdu——3861 The King’s Problem
The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other ...
-
POJ 1904 King&#39;s Quest 强联通分量+输入输出外挂
题意:国王有n个儿子,现在这n个儿子要在n个女孩里选择自己喜欢的,有的儿子可能喜欢多个,最后国王的向导给出他一个匹配.匹配有n个数,代表某个儿子和哪个女孩可以结婚.已知这些条件,要你找出每个儿子可以和 ...
-
HDU 4606 Occupy Cities (计算几何+最短路+二分+最小路径覆盖)
Occupy Cities Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)To ...
-
HDU 3861 The King’s Problem(tarjan缩点+最小路径覆盖:sig-最大二分匹配数,经典题)
The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other ...
随机推荐
-
Cannot set a credential for principal 'sa'. (Microsoft SQL Server,错误: 15535)
在SQL SERVER 2008上上禁用sa登录时,遇到下面错误:"Cannot set a credential for principal 'sa'. (Microsoft SQL Se ...
-
内网穿透神器ngrok——将本地项目驾到外网
相信做Web开发的同学们,经常会遇到需要将本地部署的Web应用能够让公网环境直接访问到的情况,例如微信应用调试.支付宝接口调试等.这个时候,一个叫ngrok的神器可能会帮到你,它提供了一个能够在公网安 ...
-
Android-AnsyncTask异步任务
同步和异步的概念区别: 同步,必须执行完成某个问题后才能继续执行其他的. 异步,我会去先执行其他问题,你执行完之后返回给我一个结果就可以. android中为什么要引用异步任务呢 android启动的 ...
-
2018-2019-20175334实验一《Java开发环境的熟悉》实验报告
2018-2019-20175334实验一<Java开发环境的熟悉>实验报告 一.实验内容及步骤 实验一Java开发环境的熟悉-1 建立"自己学号exp1"的目录 在& ...
-
C学习笔记-一些知识
memset可以方便的清空一个结构类型的变量或数组. 如: struct sample_struct { ]; int iSeq; int iType; }; 对于变量 struct sample_s ...
-
hdu4942线段树模拟rotate操作+中序遍历 回头再做
很有意思的题目,详细题解看这里 https://blog.csdn.net/qian99/article/details/38536559 自己的代码不知道哪里出了点问题 /* rotate操作不会改 ...
-
火狐浏览器报错“support.mozilla.org
火狐浏览器有时候再打开新网页会报此错“support.mozilla.org 有时候火狐浏览器会出现如下状况 解决方法 在地址栏键入”about:config” 点击“我了解此风险” 在下方任意位置右 ...
-
centOS 6.5上安装mysql5.7压缩版
mysql-5.7.10-linux-glibc2.5-i686.tar.gz是目前最新版,二进制发布包,适合各种32为版本的发型版Linux,由于只有一个包,解压后配配就行,很方便,比较符合我的风格 ...
-
mybatis映射文件mapper.xml的写法(collections...)
转自:https://blog.csdn.net/two_people/article/details/51759881 在学习mybatis的时候我们通常会在映射文件这样写: <?xml ve ...
-
js API
从基础知识JS-web-API js基础知识:ECMA 262标准 js-web-API: w3c标准 W3c标准中关于js的规定有 DOM操作.BOM操作.事件绑定.ajax请求(包括http协议) ...