question:
听说lcy帮大家预定了新马泰7日游,Wiskey真是高兴的夜不能寐啊,他想着得快点把这消息告诉大家,虽然他手上有所有人的联系方式,但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式,这样他可以通知其他人,再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人,至少得花多少电话费就能让所有人都被通知到吗?
Input多组测试数组,以EOF结束。
第一行两个整数N和M(1<=N<=1000, 1<=M<=2000),表示人数和联系对数。
接下一行有N个整数,表示Wiskey联系第i个人的电话费用。
接着有M行,每行有两个整数X,Y,表示X能联系到Y,但是不表示Y也能联系X。
Output输出最小联系人数和最小花费。
每个CASE输出答案一行。
Sample Input
12 16 2 2 2 2 2 2 2 2 2 2 2 2 1 3 3 2 2 1 3 4 2 4 3 5 5 4 4 6 6 4 7 4 7 12 7 8 8 7 8 9 10 9 11 10
Sample Output
3 6
题意:强联通分量内部是可以互相到达的,所以题目要求可转化为寻找强联通分量(tarjan算法),然后还要满足打电话花费最少
tarjan算法模板:
int dfn[maxn],low[maxn],stk[maxn],index=0,sccnum=0,top=0; void tarjan(int root){ if(dfn[root]) return; dfn[root]=low[root]=++index; stk[++top]=root; for(int i=head[root];~i;i=e[i].ne){ int v=e[i].to; if(!dfn[v]){ tarjan(v); low[root]=min(low[root],low[v]); } else if(!scc[v]){ low[root]=min(low[root],dfn[v]); } } if(low[root]==dfn[root]){ sccnum++; for(;;){int x=stk[top--]; scc[x]=sccnum; if(x==root) break; } } }
solution:
#include <cstdio> #include <vector> #include<algorithm> using namespace std; #define inf 0x3f3f3f3f #define maxn 10010 int n,m; vector<int> g[maxn]; int sccnum; int top; int index; int low[maxn],dfn[maxn],belong[maxn],stk[maxn]; bool instack[maxn]; int in[maxn],out[maxn],cost[maxn],ans[maxn]; void Init() { sccnum=0,top=0,index=0; for(int i=1; i<=n; i++) { in[i]=out[i]=0; ans[i]=inf; g[i].clear(); low[i]= dfn[i]= 0; } } void Tarjan(int root) { stk[top++]= root; instack[root]= 1; low[root]= dfn[root]= ++index; for(int i=0; i<g[root].size(); i++) { int v= g[root][i]; if( !dfn[v] ) //如果v结点未访问过 { Tarjan(v); low[root]= min( low[v], low[root] ); } else if( instack[v] ) //如果还在栈内 low[root]= min( low[root], dfn[v] ); } if( low[root]==dfn[root] ) //后代不能找到更浅的点 { ++sccnum; int x; while(1){ x= stk[--top]; instack[x]= 0; belong[x]= sccnum; ans[sccnum]=min(ans[sccnum],cost[x]); if(root==x) break; } } } int main() { while(~scanf("%d%d",&n,&m)) { Init(); for(int i=1;i<=n;i++) scanf("%d",&cost[i]); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); } for(int i=1;i<=n;i++) { if(!dfn[i]) Tarjan(i); } int ant=0,sum=0; for(int i=1;i<=n;i++) { for(int j=0;j<g[i].size();j++) { int v=g[i][j]; if(belong[i]!=belong[v]) { out[belong[i]]++, in[belong[v]]++; } } } for(int i=1;i<=sccnum;i++) { if(!in[i]) { ant++; sum+=ans[i]; } } printf("%d %d\n",ant,sum); } return 0; }