<題目鏈接>

題目大意：

一個有向圖，讓你按規則劃分區域，要求劃分的區域數最少。

規則如下：1.所有點只能屬于一塊區域；2，如果兩點相互可達，則這兩點必然要屬于同一區域；3，區域內任意兩點至少有一方能夠到達另一方。

解題分析：

雙連通的兩點必須要屬于一塊區域，所以可以直接對相互連通的點進行縮點，然后再分析縮點后的圖像，因為題目要求劃分的區域最少，且區域內的"點"之間至少有一方能夠到達另一方。仔細思考后，發現就是對縮點后的圖求最小路徑覆蓋。區域內的"點"至少要有一方能夠到達另一方，所以"點"之間連接的道路就可以看成他們之間的匹配關系。圖的最小路徑覆蓋=總點數-最大匹配數。

1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 #include <cstring> 6 using namespace std; 7 8 #define clr(a,b) memset(a,b,sizeof(a)) 9 #define rep(i,s,t) for(int i=s;i<=t;i++) 10 #define pb push_back 11 const int N = 5e3+10; 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 vector<int>vt[N],G[N]; 16 17 void init(){ 18 top=scc=tot=0; 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 i=0; i<vt[u].size(); i++){ 25 int v=vt[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 v=stk[top--]; 36 instk[v]=0; 37 belong[v]=scc; 38 if(v==u)break; 39 } 40 } 41 } 42 bool dfs(int u){ 43 for(int i=0; i<G[u].size(); i++){ 44 int v=G[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 res=0; 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 i=0; i<=n; 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 i=0;i<vt[u].size();i++){ 77 int v=vt[u][i]; 78 if(belong[u]!=belong[v]) 79 G[belong[u]].pb(belong[v]); 80 } 81 int res=Hungary(); 82 printf("%d\n",scc-res); //求出縮點后的"點"的最小路徑覆蓋 83 } 84 }

?

?

2018-11-27

轉載于:https://www.cnblogs.com/00isok/p/10029254.html

總結

以上是生活随笔為你收集整理的HDU 3861 The King’s Problem (强连通缩点+DAG最小路径覆盖)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。