n个人m条有向边

每条边有权值（话费）

在强连通分量里面互相打电话不用钱

 

求最小电话费联系到所有人

 

先缩点

一开始用了krustral最小生成树 但是时错的  因为是有向边  不是无向边！！！！！hack 三个点 1-2 权值1，1-3权值5，3-2权值4 

因为保证有答案  直接维护dis可以做

 为简单树形图

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define pb push_back#define REP(i,N)  for(int i=0;i<(N);i++)#define CLR(A,v)  memset(A,v,sizeof A)//#define inf 0x3f3f3f3fconst int N=50000+5;const int M=2*N;int head[M],pos;struct Edge{    int nex,to,v;}edge[M];struct node{    int s,e,v;}s[M];void add(int a,int b,int c){    edge[++pos].nex=head[a];    head[a]=pos;    edge[pos].v=c;    edge[pos].to=b;}int tot,ind,cnt,Stack[N],dfn[N],low[N],vis[N],belong[N];int dis[N];void init(){    tot=ind=cnt=pos=0;    CLR(Stack,0);    CLR(head,0);    CLR(vis,0);    CLR(dfn,0);    CLR(low,0);}void tarjan(int x){    dfn[x]=low[x]=++tot;    Stack[++ind]=x;    vis[x]=1;    for(int i=head[x];i;i=edge[i].nex)    {        int v=edge[i].to;        if(!dfn[v])        {            tarjan(v);            low[x]=min(low[x],low[v]);        }        else if(vis[v])            low[x]=min(low[x],low[v]);    }    if(dfn[x]==low[x])    {        cnt++;int v;        do        {            v=Stack[ind--];            vis[v]=0;            belong[v]=cnt;        }        while(x!=v);    }}int main(){    int n,m;    while(RII(n,m)==2)    {        init();        rep(i,1,m)        {            int a,b,c;RIII(a,b,c);            a++;b++;            add(a,b,c);        }        rep(i,1,n)        if(!dfn[i])tarjan(i);        rep(i,1,cnt)dis[i]=inf;        rep(i,1,n)        {            int u=belong[i];            for(int j=head[i];j;j=edge[j].nex)            {                int v=belong[ edge[j].to ];                if(u!=v)                {                    dis[v]=min(dis[v],edge[j].v);                }            }        }        int ans=0;        rep(i,1,cnt)        {            if(dis[i]!=inf)                ans+=dis[i];        }        cout<
          
           <