HDU1827 Summer Holiday（强连通缩点建图）

HDU最可爱的地方就是他的原创题目的中文描述，哎，还是母语看着亲切啊，老毛子的文字很纠结啊……

还是强连通缩点建图，tarjan实现，算是经典应用了也

建完图，找所有入度为0的点，就是最少要得到信息的点，然后这个点的权值是这个强连通分量里面所有点权值中的最小值，把他们加起来就好了。

代码：

#include<cstdio>
#include<cstring>
#include<stack>
#include<climits>
using namespace std;

const int N = 1001;

struct Edge{
 int s,e,next;
}edge1[2*N],edge2[2*N];

int n,m,e_num1,e_num2,vis_num,cnt;
int head[N],tim[N],low[N],instack[N],belong[N],price[N],de[N];

void AddEdge(int a,int b,Edge edge[],int &e_num){
 edge[e_num].s=a; edge[e_num].e=b; edge[e_num].next=head[a]; head[a]=e_num++;
}

void getmap(){
 int i,a,b;
 for(i=1;i<=n;i++)
  scanf("%d",&price[i]);
 e_num1=0;
 memset(head,-1,sizeof(head));
 while(m--){
  scanf("%d%d",&a,&b); 
  AddEdge(a,b,edge1,e_num1);
 }
}

stack <int> st;
void tarjan(int x){//注意这是个递归过程
 int i,j;
 tim[x]=low[x]=++vis_num;//tim是时间戳,标记该点出现的时间,low是该点能到达的点中时间戳值的最小值
 st.push(x);
 instack[x]=1;
 for(i=head[x];i!=-1;i=edge1[i].next){
  int u=edge1[i].e;
  if(tim[u]==-1){//时间戳为-1,也就是没有访问过
   tarjan(u);
   if(low[x]>low[u])low[x]=low[u];//更新low值,取能到达的最上(小)位置
  }
  //点u已经访问过且在栈中,时间戳比点i小,那么low值当然比点i小
  //(因为tim,low都初始化为vis_num),那么low[i]可以更新
  else if(instack[u] && tim[u]<low[x])
   low[x]=tim[u];
 }
 if(tim[x]==low[x]){
  cnt++;
  do{//退栈,直到看到根为止
   j=st.top();
   st.pop();
   instack[j]=0;
   belong[j]=cnt;//标记该点所属分量的标号
  }while(j!=x);
 }
}

int fun(int x){
 int i,min=INT_MAX;
 for(i=1;i<=n;i++){
  if(belong[i]==x && price[i]<min)
   min=price[i];
 }
 return min;
}

void solve(){
 int i;
 cnt=vis_num=0;
 memset(tim,-1,sizeof(tim));
 memset(low,0,sizeof(low));
 memset(instack,0,sizeof(instack));
 for(i=1;i<=n;i++){
  if(tim[i]==-1)tarjan(i);
 }
 
 e_num2=0;
 memset(head,-1,sizeof(head));
 memset(de,0,sizeof(de));
 for(i=0;i<e_num1;i++){
  int j=edge1[i].s;
  int k=edge1[i].e;
  if(belong[j] != belong[k]){
   AddEdge(belong[j],belong[k],edge2,e_num2);
   de[belong[k]]++;
  }
 }
 int sum=0,count=0;
 for(i=1;i<=cnt;i++){
  if(de[i]==0){
   sum+=fun(i);count++;
  }
 }
 printf("%d %d\n",count,sum);
}

int main()
{
 while(~scanf("%d%d",&n,&m))
 {
  getmap();
  solve();
 }
 return 0;
}