首页 > > 程序设计 > C/C++ >

习题：codevs 2822 爱在心中解题报告

2018-06-18 00:01:50来源：未知阅读 ()

这次的解题报告是有关tarjan算法的一道思维量比较大的题目（真的是原创文章，希望管理员不要再把文章移出首页）。

这道题蒟蒻以前做过，但是今天由于要复习tarjan算法，于是就看到codevs分类强联通分量里面只有这一道题。

题目是这样的：

“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢Our Home。”

在爱的国度里有N个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自爱的情况）。爱是具有传递性的，即如果A爱B，B爱C，则A也爱C。
如果有这样一部分人，他们彼此都相爱，则他们就超越了一切的限制，用集体的爱化身成为一个爱心天使。
现在，我们想知道在这个爱的国度里会出现多少爱心天使。而且，如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的，否则输出-1。

这是一个有向图上的问题，这道题很容易看出来一个爱心天使就是一群人互相爱然后组成的有向环。既然是有向的图求强联通分量，套上tarjan就行了。不过因为后面要输出爱心天使是由哪些人构成的，所以，我们需要记录每个人在哪个爱心天使里面，具体tarjan标程就是下面这样：

 1 void dfs(int u){
 2     low[u] = dfn[u] = ++dfs_clock;
 3     s.push(u);
 4     for(int i = 0;i < g[u].size();++i){
 5         int v = g[u][i];
 6         if(!dfn[v]){
 7             dfs(v);
 8             low[u] = min(low[u],low[v]);
 9         }
10         else if(!ind[v]){
11             low[u] = min(low[u],dfn[v]);
12         }
13     }
14     if(low[u] == dfn[u]){
15         scc_cnt++;
16         while(1){
17             int x = s.top();
18             s.pop();
19             ind[x] = scc_cnt;
20             sccno[scc_cnt]++;
21             if(x == u)break;
22         }
23     }
24 }
25 void find_scc(int n){
26     dfs_clock = scc_cnt = 0;
27     for(int i = 1;i <= n;++i){
28         if(!dfn[i])dfs(i);
29     }
30 }

如果有不懂的地方，就说明是tarjan算法还是没搞懂，请先搞定tarjan算法的基础再来看这道题。

然后就是求每个爱心天使被多少个人爱着（爱心天使也被属于它自己的人们爱着）。由于爱有传递性，我们很容易能想到传递闭包的问题。具体做法就是：

1.先求出来所有的爱心天使（在这里一个人也当作是一个爱心天使，但是输出爱心天使个数的时候，一个人组成的爱心天使是不算的）和这个爱心天使由多少个人组成。

2.给每个爱心天使编号（缩点），然后建立一个以“被爱”为方向的新的有向图。

3.在新的有向图中跑SPFA（为什么不用Floyd，这个时间复杂度太高了，所以我们还是选择scc_cnt遍的SPFA，时间复杂度最坏也就是O（nke），保证是超不了时间的。SPFA在这里起到的作用就是计算每个爱心天使的爱能否传递到某个天使）。

4.统计计数，如果size[某个爱心天使] == n的话，那么就按编号从小到大遍历每个人输出这个爱心天使由哪些人组成。如果没有任何一个爱心天使的size为n的话，（用一个数记录，如果b == 0）就输出-1.

然后呈现整体代码，还是不是很长，才刚139行。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <stack>
  7 #include <vector>
  8 #include <set>
  9 #include <queue>
 10 using namespace std;
 11 const int maxn = 1005;
 12 int dfn[maxn],low[maxn],dfs_clock,n,ind[maxn],m,scc_cnt,a,b,size[maxn],sccno[maxn],tim = 0;
 13 struct edge{
 14     int u,v;
 15     edge(int a,int b):u(a),v(b){};
 16 };
 17 struct edges{
 18     int to,next,cost;
 19 }qmap[maxn<<3];
 20 vector<int>g[maxn];
 21 vector<int>gk[maxn];
 22 vector<edge>ga;
 23 int d[maxn],h[maxn];
 24 const int INF = 10000000;
 25 stack<int> s;
 26 void add(int u,int v){
 27     qmap[tim].to = v;qmap[tim].cost = 1;qmap[tim].next = h[u];h[u] = tim++;
 28 }
 29 void init(int n){
 30     memset(dfn,0,sizeof(dfn));
 31     memset(low,0,sizeof(low));
 32     memset(ind,0,sizeof(ind));
 33     memset(size,0,sizeof(size));
 34     memset(sccno,0,sizeof(sccno));
 35     memset(h,-1,sizeof(h));
 36     for(int i = 1;i <= n;++i){
 37         g[i].clear();
 38         gk[i].clear();
 39     }
 40 }
 41 void dfs(int u){
 42     low[u] = dfn[u] = ++dfs_clock;
 43     s.push(u);
 44     for(int i = 0;i < g[u].size();++i){
 45         int v = g[u][i];
 46         if(!dfn[v]){
 47             dfs(v);
 48             low[u] = min(low[u],low[v]);
 49         }
 50         else if(!ind[v]){
 51             low[u] = min(low[u],dfn[v]);
 52         }
 53     }
 54     if(low[u] == dfn[u]){
 55         scc_cnt++;
 56         while(1){
 57             int x = s.top();
 58             s.pop();
 59             ind[x] = scc_cnt;
 60             sccno[scc_cnt]++;
 61             if(x == u)break;
 62         }
 63     }
 64 }
 65 void find_scc(int n){
 66     dfs_clock = scc_cnt = 0;
 67     for(int i = 1;i <= n;++i){
 68         if(!dfn[i])dfs(i);
 69     }
 70 }
 71 void spfa(int x){
 72     for(int i = 1;i <= scc_cnt;++i){
 73         d[i] = INF;
 74     }
 75     bool visit[maxn];
 76     memset(visit,false,sizeof(visit));
 77     d[x] = 0;
 78     queue<int>q;
 79     q.push(x);
 80     visit[x] = true;
 81     while(!q.empty()){
 82         int y = q.front();
 83         q.pop();visit[y] = false;
 84         for(int i = h[y];i != -1;i = qmap[i].next){
 85             edges e = qmap[i];
 86             if(d[y] + e.cost < d[e.to]){
 87                 d[e.to] = d[y] + e.cost;
 88                 if(!visit[e.to]){
 89                     q.push(e.to);
 90                     visit[e.to] = true;
 91                 }
 92             }
 93         }
 94     }
 95 }
 96 void work(int i){
 97     spfa(i);
 98     for(int k = 1;k <= scc_cnt;++k){
 99         if(k == i)continue;
100         if(d[k] == INF)continue;
101         size[i] += sccno[k];
102     }
103     if(size[i] == n){
104         b = 1;
105         for(int j = 1;j <= n;++j){
106             if(ind[j] == i)printf("%d ",j);
107         }
108         printf("\n");
109     }
110     return;
111 }
112 int main(){
113     scanf("%d%d",&n,&m);
114     init(n);
115     for(int i = 1;i <= m;++i){
116         scanf("%d%d",&a,&b);
117         g[a].push_back(b);
118         gk[b].push_back(a);
119         ga.push_back(edge(b,a)); 
120     }
121     find_scc(n);
122     int ans = scc_cnt;
123     for(int i = 1;i <= scc_cnt;++i){
124         if(sccno[i] == 1)ans--;
125     }
126     printf("%d\n",ans);
127     for(int i = 0;i < ga.size();++i){
128         add(ind[ga[i].u],ind[ga[i].v]);
129     }
130     for(int i = 1;i <= scc_cnt;++i){
131         size[i] = sccno[i];
132     }
133     b = 0;
134     for(int i = 1;i <= scc_cnt;++i){
135         if(sccno[i] != 1)work(i);
136     }
137     if(b == 0)printf("-1\n");
138     return 0;
139 }