最小点基和最小权点基

　　百度一下，发现这方面的资料太少。最小权点基貌似没有。

　　这两类问题都需要强连通分量来解决。强连通的模版（三个）在我博客的模版分类中有。

点基：在有向图G=（G,V）中，B是V的子集。如果对于任意的y属于V,不属于B，都存在一个x属于B，使得x是y的前代（有一条边从x到y）,则称B是一个点基。

PS：做题的时候间接相连也算。也就是有一条路径从x到y。

最小点基：顶点最少的点基。

最小权点基：顶点对应的权值之和最小的点基。（顶点权值非负）

最高强连通分量：顶点数目不能增加的强连通分量。（自己理解的）

求最小点基的步骤：

①找出图G的所有强连通分量。

②从强连通分量中找出所有的最高强连通分量。也就是缩点后入度为0的点。

③从每个最高强连通分量中任取一点，组成点集B就是一个最小点基。

求最小权点基的步骤：

①找出图G的所有强连通分量。

②从强连通分量中找出所有的最高强连通分量。也就是缩点后入度为0的点。

③从每个最高强连通分量中取权值最小的点，组成点集B就是一个最小点权基。

下面是求最小点基的一个例子。

poj1236

题目大意：

有N个学校，从每个学校都能从一个单向网络到另外一个学校，前代可以向后代（后代的后代）发送信息。

回答两个问题：
　　1：至少需要向多少个学校发放软件，才能使得网络内所有的学校最终都能得到软件。
　　2：至少需要添加几条边，才能使得任意一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

第一问很显然就是求最小点基。

第二问就是问增加几条边以后可以使某个图成为强连通分量。经过测试，答案是max(a,b),其中a是入度为0的点的个数，b是出度为0的点的个数。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const int N =110, M=50010;
  8 struct node
  9 {
 10     int to, next;;
 11 }edge[M];
 12 int head[N], low[N], dfn[N], sta[N], belg[N], num[N];
 13 bool vis[N];
 14 int scc,index,top, tot;
 15 void tarbfs(int u)
 16 {
 17     int i,j,k,v;
 18     low[u]=dfn[u]=++index;
 19     sta[top++]=u;
 20     vis[u]=1;
 21     for(i=head[u];i!=-1;i=edge[i].next)
 22     {
 23         v=edge[i].to;
 24         if(!dfn[v])
 25         {
 26             tarbfs(v);
 27             if(low[u]>low[v]) low[u]=low[v];
 28         }
 29         else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v];
 30     }
 31     if(dfn[u]==low[u])
 32     {
 33         scc++;
 34         do
 35         {
 36             v=sta[--top];
 37             vis[v]=0;
 38             belg[v]=scc;
 39             num[scc]++;
 40         }
 41         while(v!=u) ;
 42     }
 43 }
 44 void Tarjan(int n)
 45 {
 46     memset(dfn,0,sizeof(dfn));
 47     memset(low,0,sizeof(low));
 48     memset(vis,0,sizeof(vis));
 49     index=scc=top=0;
 50     for(int i=1;i<=n;i++)
 51         if(!dfn[i]) tarbfs(i);
 52 }
 53 int od[N],id[N];
 54 void init()
 55 {
 56     tot=0;
 57     memset(head,-1,sizeof(head));
 58     memset(od,0,sizeof(od));
 59     memset(id,0,sizeof(id));
 60     memset(belg,0,sizeof(belg));
 61     memset(num,0,sizeof(num));
 62 }
 63 void addedge(int i,int j)
 64 {
 65     edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;
 66 }
 67 int main()
 68 {
 69     //freopen("test.txt","r",stdin);
 70     int n,i,j,a,b,c;
 71     while(scanf("%d",&n)!=EOF)
 72     {
 73         init();
 74         for(i=1;i<=n;i++)
 75         {
 76             while(scanf("%d",&a),a) {addedge(i,a);}
 77         }
 78         Tarjan(n);
 79         for(i=1;i<=n;i++)
 80         {
 81             for(j=head[i];j!=-1;j=edge[j].next)
 82             {
 83                 int u=edge[j].to;
 84                 if(belg[i]!=belg[u])
 85                 {
 86                     od[belg[i]]++;
 87                     id[belg[u]]++;
 88                 }
 89             }
 90         }
 91         if(scc==1) {printf("1
0
"); continue;}
 92         int ans=0;
 93         a=b=0;
 94         for(i=1;i<=scc;i++)
 95         {
 96             if(od[i]==0) a++;
 97             if(id[i]==0) b++;
 98         }
 99         printf("%d
%d
",b,max(a,b));
100     }
101     return 0;
102 }

View Code

最小权点基的例子。

hdu1827 Summer Holiday

题意：（中问题）

　　一个人需要传递消息给很多人，传递给每个人的都需要花费一定的费用，得到消息的人可以把消息传递给其他人（单向的），问他（她）最少需要向多少人传消息以及最小的花费是多少。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const int N =1010, M=100010,INF=0x3f3f3f3f;
  8 struct node
  9 {
 10     int to, next;
 11 }edge[M];
 12 int head[N], low[N], dfn[N], sta[N], belg[N], num[N];
 13 int f[N], id[N],ans[N];
 14 bool vis[N];
 15 int scc,index,top, tot;
 16 void tarbfs(int u)
 17 {
 18     int i,j,k,v;
 19     low[u]=dfn[u]=++index;
 20     sta[top++]=u;
 21     vis[u]=1;
 22     for(i=head[u];i!=-1;i=edge[i].next)
 23     {
 24         v=edge[i].to;
 25         if(!dfn[v])
 26         {
 27             tarbfs(v);
 28             if(low[u]>low[v]) low[u]=low[v];
 29         }
 30         else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v];
 31     }
 32     if(dfn[u]==low[u])
 33     {
 34         scc++;
 35         do
 36         {
 37             v=sta[--top];
 38             vis[v]=0;
 39             belg[v]=scc;
 40             ans[scc]=min(ans[scc],f[v]);
 41             num[scc]++;
 42         }
 43         while(v!=u) ;
 44     }
 45 }
 46 void Tarjan(int n)
 47 {
 48     memset(vis,0,sizeof(vis));
 49     memset(dfn,0,sizeof(dfn));
 50     memset(num,0,sizeof(num));
 51     memset(low,0,sizeof(low));
 52     index=scc=top=0;
 53     for(int i=1;i<=n;i++)
 54         if(!dfn[i]) tarbfs(i);
 55 }
 56 void init()
 57 {
 58     tot=0;
 59     memset(head,-1,sizeof(head));
 60     memset(id,0,sizeof(id));
 61 }
 62 void addedge(int i,int j)
 63 {
 64     edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;
 65 }
 66 
 67 int main()
 68 {
 69     //freopen("test.txt","r",stdin);
 70     int n,m,i,j,k;
 71     while(scanf("%d%d",&n,&m)!=EOF)
 72     {
 73         init();
 74         for(i=1;i<=n;i++) ans[i]=INF;
 75         for(i=1;i<=n;i++) scanf("%d",&f[i]);
 76         while(m--)
 77         {
 78             scanf("%d%d",&i,&j);
 79             addedge(i,j);
 80         }
 81         Tarjan(n);
 82         for(i=1;i<=n;i++)
 83         {
 84             for(k=head[i];k!=-1;k=edge[k].next)
 85             {
 86                 if(belg[i]!=belg[edge[k].to]){
 87                     id[belg[edge[k].to]]++;
 88                 }
 89 
 90             }
 91         }
 92         j=k=0;
 93         for(i=1;i<=scc;i++)
 94         {
 95             if(id[i]==0)
 96             {
 97                 j++;
 98                 k+=ans[i];
 99             }
100         }
101         printf("%d %d
",j,k);
102     }
103     return 0;
104 }

View Code

这题中在统计最小的花费的时候用了点技巧，就是在求强连通分量的时候就把每个强连通分量里的最小的花费记录下来。