2233.   WTommy's Trouble

Time Limit: 2.0 Seconds   Memory Limit: 65536K

Total Runs: 1499   Accepted Runs: 437

 

As the captain, WTommy often has to inform all the TJU ACM team members of something important. But it will cost much time to inform all the members one by one. So WTommy chooses some people to inform, then he lets them inform all the people they know, and these informed people will inform more people. At last all the people will be informed.

Given the time cost to inform each person at the beginning, WTommy wants to find the minimum time he has to spend, so that at last all the people will be informed. Because the number of people can be as large as ten thousand, (eh... Maybe all the students in the university will join the ACM team? ) WTommy turns to you for help.

Please note it's possible that A knows B but B doesn't know A.

Input

The first line of each test case contains two integers N and M, indicating the number of people and the number of relationships between them. The second line contains N numbers indicating the time cost to inform each people. Then M lines followed, each contains two numbers A_i and B_i, indicating that A_i knows B_i.

You can assume that 1 ≤ N ≤ 10000, 0 ≤ M ≤ 200000. The time costs for informing each people will be positive and no more than 10000. All the people are numbered from 1 to N.

The input is terminated by a line with N = M = 0.

Output

Output one line for each test case, indicating the minimum time WTommy has to spend.

Sample Input

 

4 330 20 10 401 22 12 30 0

 

Sample Output

 

60

 

Hint

For the sample input, WTommy should inform two members, No.2 and No.4, which costs 20 + 40 = 60.

Author: RoBa

Source: 

 

解题：强连通缩点求出每个强连通分量的最小值，然后看缩点后入度为0的点的值的和

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 const int maxn = 10010; 8 const int INF = 0x3f3f3f3f; 9 vector
           
            g[maxn];10 int belong[maxn],dfn[maxn],low[maxn],idx,scc;11 int n,m,minV[maxn],val[maxn],in[maxn];12 bool instack[maxn];13 stack
            
             stk;14 void init(){15 for(int i = 0; i < maxn; ++i){16 dfn[i] = low[i] = belong[i] = 0;17 instack[i] = false;18 in[i] = 0;19 g[i].clear();20 }21 idx = scc = 0;22 while(!stk.empty()) stk.pop();23 }24 void tarjan(int u){25 dfn[u] = low[u] = ++idx;26 instack[u] = true;27 stk.push(u);28 for(int i = g[u].size()-1; i >= 0; --i){29 if(!dfn[g[u][i]]){30 tarjan(g[u][i]);31 low[u] = min(low[u],low[g[u][i]]);32 }else if(instack[g[u][i]]) low[u] = min(low[u],dfn[g[u][i]]);33 }34 if(low[u] == dfn[u]){35 int v;36 scc++;37 minV[scc] = INF;38 do{39 instack[v = stk.top()] = false;40 stk.pop();41 belong[v] = scc;42 minV[scc] = min(minV[scc],val[v]);43 }while(v != u);44 }45 }46 int main(){47 int u,v;48 while(scanf("%d %d",&n,&m),n||m){49 init();50 for(int i = 1; i <= n; ++i)51 scanf("%d",val+i);52 for(int i = 0; i < m; ++i){53 scanf("%d %d",&u,&v);54 g[u].push_back(v);55 }56 for(int i = 1; i <= n; ++i)57 if(!dfn[i]) tarjan(i);58 int ans = 0;59 for(int i = 1; i <= n; ++i)60 for(int j = g[i].size()-1; j >= 0; --j)61 if(belong[i] != belong[g[i][j]]) in[belong[g[i][j]]]++;62 for(int i = 1; i <= scc; ++i)63 if(!in[i]) ans += minV[i];64 printf("%d\n",ans);65 }66 return 0;67 }