Tarjan缩点后求入度为0的点，即是要求最少电话。
#include#include #include #include using namespace std;int cst[1010];struct Edge{ int u,v; int next;}edge[2010];int head[1010],dfn[1010],low[1010],stack[1010],st;bool instack[1010];int tot,nTime,ans,btn;int n,m;int belong[1010],label[1010];int edsave[2010][2];int degree[1010];void addedge(int u,int v){ edge[tot].u=u; edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++;}void tarjan(int u,int ufa){ dfn[u]=low[u]=++nTime; stack[++st]=u; instack[u]=true; for(int e=head[u];e!=-1;e=edge[e].next){ int v=edge[e].v; if(dfn[v]==-1){ tarjan(v,u); low[u]=min(low[u],low[v]); } else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ int v; int mincst=(1<<30)-1; btn++; do{ v=stack[st--]; instack[v]=false; belong[v]=btn; mincst=min(mincst,cst[v]); }while(u!=v); label[btn]=mincst; }}int main(){ int u,v; while(scanf("%d%d",&n,&m)!=EOF){ memset(head,-1,sizeof(head)); memset(dfn,-1,sizeof(dfn)); memset(low,-1,sizeof(low)); memset(instack,false,sizeof(instack)); memset(degree,0,sizeof(degree)); st=tot=nTime=ans=btn=0; for(int i=1;i<=n;i++) scanf("%d",&cst[i]); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); edsave[i][0]=u; edsave[i][1]=v; addedge(u,v); } for(int i=1;i<=n;i++){ if(dfn[i]==-1){ tarjan(i,0); } } for(int i=1;i<=m;i++){ if(belong[edsave[i][0]]==belong[edsave[i][1]]) continue; else degree[belong[edsave[i][1]]]++; } int cnt=0; for(int i=1;i<=btn;i++) if(degree[i]==0){ cnt++; ans+=label[i]; } printf("%d %d\n",cnt,ans); } return 0;}