（有向图）有环不花费，没环有花费，求使所有点连通最小花费。（保证从0节点可以到达任何节点&&图是连通的）
一眼秒错解！！！！！！！
打了个缩点+kuskal，然后自己以为能AC然后完美得到10分
正解，贪心+缩点。
因为保证0可以到任何节点
每次取出当前点入边最小值，得到图依然保持连通，所以贪心正确。
#include<bits/stdc++.h> #define ll long long #define A 1000000 using namespace std; ll sta[A],low[A],dfn[A],belong[A],head[A],nxt[A],ver[A],edg[A]; ll head_c[A],nxt_c[A],ver_c[A],edg_c[A],minn[A]; ll cnt=0,top=0,num=0,n,m,ans=0,sd=0,tot_c=0,tot=0; bool ins[A],flag[A]; void add(ll x,ll y,ll z){ nxt[++tot]=head[x],head[x]=tot,ver[tot]=y,edg[tot]=z; } void add_c(ll x,ll y,ll z){ nxt_c[++tot_c]=head_c[x],head_c[x]=tot_c,ver_c[tot_c]=y,edg_c[tot_c]=z; } void rebuilt(){ for(ll i=0;i<n;i++) for(ll j=head[i];j;j=nxt[j]){ ll y=ver[j]; if(belong[i]!=belong[y]){ minn[belong[y]]=min(edg[j],minn[belong[y]]); } } } void tarjan(ll x){ low[x]=dfn[x]=++num; sta[++top]=x;ins[x]=1; for(ll i=head[x];i;i=nxt[i]){ ll y=ver[i]; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); } else if(ins[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ ll yy=0; cnt++; while(1){ yy=sta[top--]; belong[yy]=cnt; ins[yy]=0; if(yy==x) break; } } } void re(){ top=0,num=0,cnt=0,tot=0,sd=0,tot_c=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(flag,0,sizeof(flag)); memset(head,0,sizeof(head)); memset(ver,0,sizeof(ver)); memset(belong,0,sizeof(belong)); memset(ins,0,sizeof(ins)); memset(minn,0x3f,sizeof(minn)); memset(head_c,0,sizeof(head_c)); memset(nxt_c,0,sizeof(nxt_c)); } int main(){ // freopen("message3.in","r",stdin); // freopen("w.out","w",stdout); while(1){ scanf("%lld%lld",&n,&m); if(n==m&&n==0) return 0; ans=0; re(); for(ll i=1;i<=m;i++){ ll xx,yy,zz; scanf("%lld%lld%lld",&xx,&yy,&zz); add(xx,yy,zz); } for(ll i=0;i<n;i++) if(!dfn[i]) tarjan(i); rebuilt(); for(ll i=1;i<=cnt;i++) { if(minn[i]<=110000) ans+=minn[i]; } printf("%lld\n",ans); } } View Code
转载于:https://www.cnblogs.com/znsbc-13/p/11196781.html
相关资源：Netty即时通讯项目Demo