思路：
以上纯属水博客
有强连通分量这个算法提示，思路应该不难想
但是有一个小细节
我们枚举入边的时候要缩点之后反向建图，然后枚举出边
我没建反图调了一辈子
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e4+5,maxm=1e5+5;
int n,m,bcnt,ecnt,tmp,cnt,st[maxn],top,head[maxn],head1[maxn],dfn[maxn],ans;
int low[maxn],c[maxn],out[maxn];
bool v[maxn];
struct edge
{
int from,to,nxt,w;
}e[maxm],b[maxm];
void add(int x,int y,int z)
{
b[++bcnt]=(edge){x,y,head[x],z};
head[x]=bcnt;
}
void add1(int x,int y,int z)
{
// printf("u:%d v:%d w:%d\n",x-1,y-1,z);
e[++ecnt]=(edge){x,y,head1[x],z};
head1[x]=ecnt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++cnt;v[x]=1;
st[++top]=x;
for(int i=head[x];i;i=b[i].nxt)
{
int y=b[i].to;
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(v[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
tmp++;
do
{
c[st[top]]=tmp;
v[st[top]]=0;
top--;
}while(x!=st[top+1]);
}
}
void clear()
{
memset(st,0,sizeof(st));
memset(head,0,sizeof(head));
memset(head1,0,sizeof(head1));
memset(dfn,0,sizeof(dfn));
memset(c,0,sizeof(c));
memset(v,0,sizeof(v));
memset(low,0,sizeof(low));
ecnt=0;bcnt=0;tmp=0;cnt=0;top=0;ans=0;
}
void work()
{
for(int u=1;u<=tmp;u++)
{
int flag=0;
if(!out[u]) continue;
int minn=0x7fffffff;
// cout<<head1[u]<<endl;
for(int i=head1[u];i;i=e[i].nxt) minn=min(minn,e[i].w),flag=1;
// cout<<out[u]<<" "<<flag<<" "<<minn<<endl;
if(flag) ans+=minn;
}
}
signed main()
{
while(1)
{
scanf("%lld%lld",&n,&m);
if(n==0&&m==0) break;
clear();
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x+1,y+1,z);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
// for(int i=1;i<=n;i++) cout<<c[i]<<" ";
// cout<<endl;
for(int i=1;i<=bcnt;i++)
{
int x=b[i].from,y=b[i].to,z=b[i].w;
if(c[x]!=c[y]) add1(c[y],c[x],z),out[c[y]]++;
}
// cout<<tmp<<endl;
// for(int i=1;i<=n;i++) cout<<out[i]<<" ";
// cout<<endl;
work();
printf("%lld\n",ans);
}
return 0;
}
/*
7 6
0 1 22622
0 2 60946
2 3 12288
2 4 60583
0 5 22206
2 6 65358
244003
*/