杭电1827

很久很久没有写过题解了，题解还是要多写，要多总结。
题意：Wiskey知道他所有朋友的联系方式，知道他的朋友都有谁的联系方式，也知道联系他们要用的话费。现在他要通知所有朋友，最少要通知多少人，最少用多少电话费才够？
Input
多组测试数组，以EOF结束。
第一行两个整数N和M（1<=N<=1000, 1<=M<=2000），表示人数和联系对数。
接下一行有N个整数，表示Wiskey联系第i个人的电话费用。
接着有M行，每行有两个整数X，Y，表示X能联系到Y，但是不表示Y也能联系X。

Output
输出最小联系人数和最小花费。
每个CASE输出答案一行。

分析：一开始以为人数最少和话费最少要分两种不同的情况来算，后来发现话费最少的时候人数也是最少的。因为以人为节点，两人之间的联系方式为弧，建出来的有向图里，对于强连通分支，要且仅要通知里面任意一个人，那么这个强连通分支里面的所有人都能通知到，所以人数的最少代价是1，而通知话费最低的人能使话费代价最低。把强连通分支缩点，图就变成一堆单向连通分支了。每一个单向连通分支里面要且仅要通知入度为0的那个人，那么这个连通分支里面的所有人都能通知到，这是通知这些人代价最低的方法。

杭电1827-编程知识网 View Code

 1 #include<cstdio>
 2 #include<vector>
 3 #include<stack>
 4 using std::stack;
 5 using std::vector;
 6 vector<int> arc[1001];
 7 stack<int> s;
 8 bool visited[1001],instack[1001],root[1001];
 9 int n,m,exp[1001],low[1001],num[1001],set[1001],root_exp[1001],rn,counter,minCall,minExp;
10 int min(const int a,const int b)
11 {
12     return a>b?b:a;
13 }
14 void tarjan(int u)
15 {
16     int v,i;
17     num[u]=low[u]=++counter;
18     visited[u]=true;
19     instack[u]=true;
20     s.push(u);
21     for(i=0;i<arc[u].size();i++)
22     {
23         v=arc[u][i];
24         if(!visited[v])
25         {
26             tarjan(v);
27             low[u]=min(low[u],low[v]);
28         }
29         else if(instack[v])
30             low[u]=min(low[u],num[v]);
31         if(root[v])
32             root_exp[set[v]]=0;
33     }
34     if(num[u]==low[u])
35     {
36         root_exp[rn]=0xffffff;
37         do
38         {
39             v=s.top();
40             set[v]=rn;
41             root[v]=true;
42             if(root_exp[rn]>exp[v])
43                 root_exp[rn]=exp[v];
44             instack[v]=false;
45             s.pop();
46         }while(u!=v);
47         rn++;
48     }
49 }
50 int main()
51 {
52     int i,u,v;
53     while(~scanf("%d%d",&n,&m))
54     {
55         for(i=1;i<=n;i++)
56         {
57             visited[i]=false;
58             instack[i]=false;
59             root[i]=false;
60             scanf("%d",&exp[i]);
61         }
62         for(i=0;i<m;i++)
63         {
64             scanf("%d%d",&u,&v);
65             arc[u].push_back(v);
66         }
67         counter=0;
68         minCall=minExp=0;
69         rn=0;
70         for(i=1;i<=n;i++)
71         {
72             if(!visited[i])
73                 tarjan(i);
74         }
75         for(i=0;i<rn;i++)
76         {
77             if(root_exp[i] && root_exp[i]!=0xffffff)
78             {
79                 minCall++;
80                 minExp+=root_exp[i];
81             }
82         }
83         for(i=1;i<=n;i++)
84             arc[i].clear();
85     }
86     return 0;
87 }