B. 通讯
题目描述
输入格式
输出格式
样例
数据范围与提示
考虑到题解太短所以把题面粘上了……
大水题一个（然而居然没有一眼看出……），首先tarjan缩点，对于每个scc，贪心选择入边中最优解，最后答案即为最优。
至于正确性证明：考虑到点i时，如果i入度大于1，那么贪心选最优的一条边，他不会影响其他点，其他点也并不会影响i（无论如何与i相连的点都是和0联通的）。
因为是考试代码所以比较乱……
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<vector>
#include<queue>
#define ma(x) memset(x,0,sizeof(x))
#define LL long long
#define MAXN 50010
using namespace std;
struct edge
{
int u,v,w,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define w(x) ed[x].w
#define n(x) ed[x].nxt
#define u2(x) ed2[x].u
#define v2(x) ed2[x].v
#define w2(x) ed2[x].w
#define n2(x) ed2[x].nxt
}ed[MAXN*10],ed2[MAXN*10];
int first[MAXN],num_e;
#define f(x) first[x]
int first2[MAXN],num_e2;
#define f2(x) first2[x]
int n,m;
inline int read();
int dfn[MAXN],low[MAXN],num;
int stack[MAXN*2],top;
int belong[MAXN],tot;
bool v[MAXN];
int du[MAXN],cu[MAXN];
vector<int> scc[MAXN];
void tarjan(int x)
{
dfn[x]=low[x]=++num;
v[x]=1;stack[++top]=x;
for(int i=f(x);i;i=n(i))
if(!dfn[v(i)])tarjan(v(i)),low[x]=min(low[x],low[v(i)]);
else if(v[v(i)])low[x]=min(low[x],dfn[v(i)]);
if(low[x]==dfn[x])
{
++tot;v[x]=0;
while(stack[top]!=x)
{
v[stack[top]]=0;
belong[stack[top]]=tot;
scc[tot].push_back(stack[top--]);
}
belong[stack[top]]=tot;
scc[tot].push_back(stack[top--]);
}
}
int dis[MAXN],ans[MAXN];
void dfs(int x,int di)
{
// dis[x]=di;
for(int i=f2(x);i;i=n2(i))
dfs(v2(i),w2(i)),ans[x]+=ans[v2(i)];
ans[x]+=di;
// cout<<scc[x][0]-1<<" "<<ans[x]<<endl;
}
/*
void spfa(int x)
{
memset(dis,0x7f,sizeof(dis));
ma(v);
queue<int> q;
v[x]=1;dis[x]=0;
q.push(x);
while(!q.empty())
{
int k=q.front();q.pop();v[k]=0;
for(int i=f2(k);i;i=n2(i))
if(dis[v2(i)]>dis[k]+w2(i))
{
dis[v2(i)]=dis[k]+w2(i);
if(!v[v2(i)])
{
v[v2(i)]=1;
q.push(v2(i));
}
}
}
}*/
inline void add(int u,int v,int w);
inline void add2(int u,int v,int w);
signed main()//多测清空！！！！！
{
// freopen("in.txt","r",stdin);
while(cin>>n>>m)
{
if(!n&&!m)return 0;
ma(ed);ma(ed2);ma(first);ma(first2);ma(dfn);ma(low);ma(belong);ma(v);ma(du);ma(cu);ma(scc);ma(ans);
num_e=num_e2=top=num=tot=0;
int a,b,c;
for(int i=1;i<=m;i++)
{
a=read(),b=read(),c=read();
add(a+1,b+1,c);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
/* for(int i=1;i<=tot;i++)
{
printf("#%d:
",i);
for(int j=0;j<scc[i].size();j++)
cout<<scc[i][j]<<" ";
puts("");
}
*/ for(int i=1;i<=num_e;i++)
if(belong[u(i)]!=belong[v(i)])
add2(belong[u(i)],belong[v(i)],w(i)),
du[belong[v(i)]]++,cu[belong[u(i)]]++;
if(num_e2==tot-1)
{
dfs(belong[1],0);
printf("%d
",ans[belong[1]]);
continue;
}
else
{
LL eans=0;
for(int i=1;i<=num_e2;i++)
if(du[v2(i)]==1)
{
eans+=w2(i);
du[v2(i)]=0;
// cout<<"!"<<v2(i)<<" "<<du[v2(i)]<<endl;
}
// cout<<eans<<endl;
memset(ans,0x7f,sizeof(ans));
for(int i=1;i<=num_e2;i++)
if(du[v2(i)])
{
ans[v2(i)]=min(ans[v2(i)],w2(i));
// cout<<v2(i)<<" "<<ans[v2(i)]<<endl;
}
for(int i=1;i<=tot;i++)
if(du[i])
{
eans+=ans[i];
// cout<<scc[i][0]<<endl;
}
printf("%lld
",eans);
}
}
}
inline int read()
{
int s=0,f=1;char a=getchar();
while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();}
while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
return f*s;
}
inline void add(int u,int v,int w)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
w(num_e)=w;
n(num_e)=f(u);
f(u)=num_e;
}
inline void add2(int u,int v,int w)
{
++num_e2;
u2(num_e2)=u;
v2(num_e2)=v;
w2(num_e2)=w;
n2(num_e2)=f2(u);
f2(u)=num_e2;
}