越狱（break）

【问题描述】 Michael为救哥哥身陷囹圄，被关进foxriver监狱。为准备越狱，他需要散布消息给监狱中其他人来共同协作，但是监狱中鱼龙混杂，分成各个小团体，内部消息传递单向传输。问题1：初始至少需要向多少个透漏消息，使得监狱内所有人都获知消息。 问题2，至少需要添加几条传输线路(边)，使任意向一个人散步消息后，经过若干次传送，监狱内所有的人最终都能得到消息。 【输入格式】 从文件break.in中输入数据。 输入的第一行包含一个整数 N：监狱人数（2 <= N <= 100）。用前 N 个正整数标识每个人。接下来 N 行中每行都表示一个消息传递列表（分发列表）。第 i+1 行包括 i 的接收消息的人的标识符。每个列表用 0 结束。空列表只用一个 0 表示。 【输出格式】 输出到文件break.out中。 输出的第一行包含一个正整数：问题1的解。第二行应该包含问题2的解。 【样例输入】 5 2 4 3 0 4 5 0 0 0 1 0 【样例输出】 1 2

题解

问题二即为HUD2767的问题，简单来说就是tarjan跑完DAG后询问还要加多少边又可以变成变成一个强连通分量。 1. 求出所有强连通分量 2. 每个强连通分量缩成一点，则形成一个有向无环图DAG。 3. DAG上面有多少个入度为0的顶点，问题1的答案就是多少 在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少 加边的方法： 要为每个入度为0的点添加入边，为每个出度为0的点添加出边 假定有 n 个入度为0的点，m个出度为0的点，如何加边？ 把所有入度为0的点编号 0,1,2,3,4 ….N -1 每次为一个编号为i的入度0点可达的出度0点，添加一条出边，连到编号为(i+1)%N 的那个出度0点, 这需要加n条边 若 m <= n，则加了这n条边后，已经没有入度0点，则问题解决，一共加了n条边 若 m > n，则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，即可，这还需加m-n条边。 所以，max(m,n)就是第二个问题的解 此外：当只有一个强连通分支的时候，就是缩点后只有一个点，虽然入度出度为0的都有一个，但是实际上不需要增加清单的项了，所以答案是1，0；

code

#include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<algorithm> #define Mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=110; int n,m,len,Tim,cnt; stack<int> q; struct node{ int to,next; }e[maxn*maxn]; bool flag[maxn]; void Insert(int,int); void Dfs(int ); int Low[maxn],head[maxn],dfn[maxn],a[maxn]={0},ru[maxn],w[maxn],chu[maxn],Belong[maxn]; int ma(){ scanf("%d",&n); memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++){ int m; while(scanf("%d",&m),m!=0)Insert(i,m); } for(int i=1;i<=n;i++)if(dfn[i]==0)Dfs(i); for(int i=1;i<=n;i++){ int tot=0; for(int j=head[i];j!=-1;j=e[j].next){ int h=e[j].to; if(Belong[h]!=Belong[i]){ ru[Belong[h]]++; chu[Belong[i]]++; } } } int ans1=0,ans2=0; for(int i=1;i<=cnt;i++){ if(ru[i]==0)ans1++; if(chu[i]==0)ans2++; } ans2=max(ans2,ans1); for(int i=2;i<=n;i++){ if(Belong[i]!=Belong[i-1]) break; if(i==n)ans2=0; } printf("%d\n%d",ans1,ans2); } void Insert(int x,int y) { len++; e[len].to=y; e[len].next=head[x]; head[x]=len; } void Dfs(int x){ Tim++;dfn[x]=Low[x]=Tim;q.push(x);flag[x]=1; for(int i=head[x];i!=-1;i=e[i].next){ int t=e[i].to; if(dfn[t]==0){ Dfs(t); Low[x]=min(Low[x],Low[t]); } else if(flag[t]==1)Low[x]=min(Low[x],dfn[t]); } if(dfn[x]==Low[x]){ cnt++; int k=0; do{ k=q.top();q.pop(); flag[k]=0; Belong[k]=cnt; }while(k!=x); } } int hhh=ma(); int main(){;}

这种思维方式还是很值得背板子的同学们学习。