站长工具seo综合查询隐私查询,济南网站运营公司,怎样自己做网站赚钱吗,广东建筑人才网题目链接 题目大意#xff1a; 一个有向图#xff0c;让你按规则划分区域#xff0c;要求划分的区域数最少。 规则如下#xff1a;1.所有点只能属于一块区域#xff1b;2#xff0c;如果两点相互可达#xff0c;则这两点必然要属于同一区域#xff1b;3#x…题目链接 题目大意 一个有向图让你按规则划分区域要求划分的区域数最少。 规则如下1.所有点只能属于一块区域2如果两点相互可达则这两点必然要属于同一区域3区域内任意两点至少有一方能够到达另一方。 解题分析 双连通的两点必须要属于一块区域所以可以直接对相互连通的点进行缩点然后再分析缩点后的图像因为题目要求划分的区域最少且区域内的点之间至少有一方能够到达另一方。仔细思考后发现就是对缩点后的图求最小路径覆盖。区域内的点至少要有一方能够到达另一方所以点之间连接的道路就可以看成他们之间的匹配关系。图的最小路径覆盖总点数-最大匹配数。 1 #include iostream2 #include cstdio3 #include vector4 #include algorithm5 #include cstring6 using namespace std;7 8 #define clr(a,b) memset(a,b,sizeof(a))9 #define rep(i,s,t) for(int is;it;i)
10 #define pb push_back
11 const int N 5e310;
12 int dfn[N], low[N], stk[N], belong[N], vis[N], match[N];
13 bool instk[N];
14 int top, scc, tot, n, m, T;
15 vectorintvt[N],G[N];
16
17 void init(){
18 topscctot0;
19 clr(dfn,0);clr(low,0);clr(instk,false);
20 }
21 void Tarjan(int u){ //tarjan进行缩点
22 dfn[u]low[u]tot;
23 stk[top]u;instk[u]1;
24 for(int i0; ivt[u].size(); i){
25 int vvt[u][i];
26 if(!dfn[v]){
27 Tarjan(v);
28 low[u]min(low[u],low[v]);
29 }else if(instk[v])
30 low[u]min(low[u],dfn[v]);
31 }
32 if(low[u]dfn[u]){
33 scc;
34 while(true){
35 int vstk[top--];
36 instk[v]0;
37 belong[v]scc;
38 if(vu)break;
39 }
40 }
41 }
42 bool dfs(int u){
43 for(int i0; iG[u].size(); i){
44 int vG[u][i];
45 if(!vis[v]){
46 vis[v]1;
47 if(match[v]-1||dfs(match[v])){
48 match[v]u;
49 return true;
50 }
51 }
52 }
53 return false;
54 }
55 int Hungary(){ //匈牙利匹配,对缩点后的点求最大匹配
56 int res0;
57 clr(match,-1);
58 rep(i,1,scc){
59 clr(vis,0);
60 if(dfs(i))res;
61 }
62 return res;
63 }
64 int main(){
65 scanf(%d,T);while(T--){
66 scanf(%d%d,n,m);
67 for(int i0; in; i) vt[i].clear();
68 rep(i,1,m){
69 int u,v;scanf(%d%d,u,v);
70 vt[u].pb(v);
71 }
72 init();
73 rep(i,1,n)
74 if(!dfn[i]) Tarjan(i); //对所有双连通的点进行缩点
75 rep(i,0,n)G[i].clear();
76 rep(u,1,n) for(int i0;ivt[u].size();i){
77 int vvt[u][i];
78 if(belong[u]!belong[v])
79 G[belong[u]].pb(belong[v]);
80 }
81 int resHungary();
82 printf(%d\n,scc-res); //求出缩点后的点的最小路径覆盖
83 }
84 } 2018-11-27转载于:https://www.cnblogs.com/00isok/p/10029254.html
