首页 > 代码库 > POJ1236 network of schools

POJ1236 network of schools

100个学校,有单向网络连接,从而分享软件。

问题一:几个学校得到软件就可使所有学校都得到?

问题二:再加几条单向网络可以使得“任意学校得到软件,就可使得所有学校都有软件”?

——————————————————————————————————————————————————————————

强连通分量内部可做到“一点得,全部得”,从而可以看做一个点,所以,缩点,得到有向无环图。

在图中,入读为0的点因为无人与他分享,所以必须直接获得——问题一答案。

想要“一点得,全部得”,就要全部点成为一个强连通分量,加边的多少由入读为0的点数和出度为0的点数的最大值决定。——问题二答案

 

注意:如果所有点本身就是强连通分量,需要特判。

——————————————————————————————————————————————————————————

 

技术分享
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stack>
 6 
 7 using namespace std;
 8 const int maxn=105;
 9 int n;
10 struct edge
11 {
12     int u,v,next;
13 }e[10005],ee[10005];
14 int head[105],headd[105],js,jss;
15 int dfsn[105],low[105],visx;
16 stack<int>st;
17 bool ins[105];
18 int chudu[105],rudu[105];
19 int sshu,belong[105];
20 void addage(int u,int v,edge e[],int head[],int &js)
21 {
22     e[++js].u=u;e[js].v=v;
23     e[js].next=head[u];head[u]=js;
24 }
25 void tarjan(int u)
26 {
27     dfsn[u]=low[u]=++visx;
28     st.push(u);
29     ins[u]=1;
30     for(int i=head[u];i;i=e[i].next)
31     {
32         int v=e[i].v;
33         if(dfsn[v]==0)
34         {
35             tarjan(v);
36             low[u]=min(low[u],low[v]);
37         }
38         else if(ins[v] && low[u]>dfsn[v])low[u]=dfsn[v];
39     }
40     if(dfsn[u]==low[u])
41     {
42         sshu++;
43         int tp;
44         do
45         {
46             tp=st.top();
47             st.pop();
48             ins[tp]=0;
49             belong[tp]=sshu;
50         }
51         while(tp!=u);
52     }
53 }
54 int main()
55 {
56     scanf("%d",&n);
57     for(int v,i=1;i<=n;i++)
58     {
59         while(scanf("%d",&v)==1 && v!=0)
60         {
61             addage(i,v,e,head,js);
62         }
63     }
64     for(int i=1;i<=n;i++)
65         if(dfsn[i]==0)tarjan(i);
66     for(int i=1;i<=js;i++)
67     {
68         int u=e[i].u,v=e[i].v;
69         if(belong[u]!=belong[v])
70         {
71             addage(belong[u],belong[v],ee,headd,jss);
72             chudu[belong[u]]++;rudu[belong[v]]++;
73         }
74     }
75     int chudu0=0,rudu0=0;
76     for(int i=1;i<=sshu;i++)
77     {
78         if(chudu[i]==0)chudu0++;
79         if(rudu[i]==0)rudu0++;
80     }
81     printf("%d\n",rudu0);
82     if(sshu==1)printf("0\n");
83     else printf("%d\n",max(chudu0,rudu0));
84     return 0;
85 }
View Code

 

POJ1236 network of schools