【HDOJ3861】【Tarjan缩点+最小路径覆盖】 The King’s Problem

http://acm.hdu.edu.cn/showproblem.php?pid=3861

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3544 Accepted Submission(s): 1256

Problem Description

In 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.

Input

The first line contains a single integer T, the number of test cases. And then followed T cases.

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

The 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.

Sample Input

1 3 2 1 2 1 3

Sample Output

题目大意：给一个无向图，1）如果u v两点互相可达，则必须被划分为同一个区域，

　　　　　　　　　　　　2）如果u 和 v 至少有一方可达另一方【并且不能经过别的区域，即所走路径必须和自己属于同一区域】则可以被划分为同一个区域

　　　　　　　　　　　　3）一个点必须属于且只属于一个区域

求所需划分的最少区域

题目分析：由要求一可知要先求强连通分量进行缩点，而要求二和三可知即求最小路径覆盖【最少用几条路径【路径即起点与终点都不相同，无相交的路】可以走过所有的点】

定义:

最小路径覆盖：在图中找一些路径（路径数最少），使之覆盖了图中所有的顶点，且每个顶点有且仅和一条路径有关联。

最小顶点覆盖：在图中找一些点（顶点数最少），使之覆盖了图中所有的边，每条边至少和一个顶点有关联。

二分图：最小顶点覆盖=最大匹配数。

最小路径覆盖=顶点数-最大匹配数。

  1 //Wannafly挑战赛14 C https://www.nowcoder.com/acm/contest/81/C
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<stack>
  7 #include<vector>
  8 using namespace std;
  9 const int maxn=100005;
 10 struct edge{
 11     int from;
 12     int to;
 13     int next;
 14 }EDGE[maxn];
 15 vector<int>vc[maxn];
 16 int head[maxn],dfn[maxn],vis[maxn],vvis[maxn],used[maxn],low[maxn],col[maxn],in[maxn],out[maxn],en[maxn],stk[maxn];//各个变量的意义可参照上篇博客
 17 int edge_cnt=1,tot1=0,tot2=0,scc_cnt=0,tot0=0;
 18 void add(int x,int y)
 19 {
 20     EDGE[edge_cnt].from=x;    
 21     EDGE[edge_cnt].to=y;
 22     EDGE[edge_cnt].next=head[x];
 23     head[x]=edge_cnt++;
 24 }
 25 bool find(int x)
 26 {
 27     for(int i = head[x] ; i != -1 ; i=EDGE[i].next)
 28     {
 29         if(!used[EDGE[i].to])
 30         {
 31             used[EDGE[i].to]=1;
 32             if(!vvis[EDGE[i].to]||find(vvis[EDGE[i].to]))
 33             {
 34                 vvis[EDGE[i].to]=x;
 35                 return 1;
 36             }
 37         }
 38     }
 39     return 0;
 40 }
 41 void Tarjan(int u)
 42 {
 43     low[u]=dfn[u]=++tot1;//注意tot1的初值必须是1【因为dfn必须为正数】，所以这里使用++tot1而不用tot1++;
 44     vis[u]=1;
 45     stk[++tot2]=u;
 46     for(int i = head[u]; i != -1  ; i = EDGE[i].next)
 47     {
 48         if(!dfn[EDGE[i].to]){
 49             Tarjan(EDGE[i].to);
 50             low[u]=min(low[u],low[EDGE[i].to]);
 51         }
 52         else if(vis[EDGE[i].to]){
 53             low[u]=min(low[u],low[EDGE[i].to]);
 54         }
 55     }
 56             if(low[u]==dfn[u]){
 57             int xx;
 58             scc_cnt++;
 59             do{
 60                 xx=stk[tot2--];
 61                 vc[scc_cnt].push_back(xx);
 62                 col[xx]=scc_cnt;
 63                 vis[xx]=0;
 64             }while(xx!=u);
 65         }
 66 }
 67 int main()
 68 {
 69     int t;
 70     scanf("%d",&t);
 71     while(t--)
 72     {
 73     edge_cnt=0,tot1=0,tot2=0,scc_cnt=0,tot0=0;    
 74      scc_cnt=0;
 75     int n,m;
 76     scanf("%d%d",&n,&m);
 77     memset(head,-1,sizeof(head));
 78     memset(stk,0,sizeof(stk));
 79     memset(in,0,sizeof(in));
 80     memset(out,0,sizeof(out));
 81     memset(dfn,0,sizeof(dfn));
 82     memset(low,0,sizeof(low));
 83     memset(col,0,sizeof(col));    
 84    memset(vis,0,sizeof(vis));  
 85     memset(vvis,0,sizeof(vvis));  
 86     while(m--)
 87     {
 88         int a,b;
 89         scanf("%d%d",&a,&b);
 90          add(a,b);
 91     }
 92     for(int i = 1 ; i <= n; i++)
 93     {
 94         if(!dfn[i])Tarjan(i);
 95     }
 96     memset(head,-1,sizeof(head));
 97     int orz0=edge_cnt;
 98  //   cout << "$$$
";
 99  edge_cnt=0;
100     for(int i = 0 ; i < orz0 ; i++)
101     {
102         if(col[EDGE[i].from]!=col[EDGE[i].to])
103         {
104             add(col[EDGE[i].from],col[EDGE[i].to]);
105 //            cout << col[EDGE[i].from] << endl;
106         }
107     }
108   //  cout << "###
";
109     int sum=0;
110     //int sum1=0,sum2=0;
111         for(int i = 1 ; i <= scc_cnt ; i++)
112         {
113             memset(used,0,sizeof(used));
114             if(find(i))sum++;
115         }
116     cout << scc_cnt-sum <<endl;
117     for(int i = 1 ; i <= scc_cnt ; i++)
118     vc[i].clear();
119 }
120     return 0;
121 }
122 /*4 5
123 1 3
124 2 4
125 4 2
126 1 4
127 2 1*/

【HDOJ3861】【Tarjan缩点+最小路径覆盖】 The King’s Problem

相关推荐