B. 通讯

题目描述

“这一切都是命运石之门的选择。”

试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短信，并由此得知了伦太郎制作出了电话微波炉（仮）。

为了掌握时间机器的技术，SERN总部必须尽快将这个消息通过地下秘密通讯网络，传达到所有分部。

SERN共有N个部门（总部编号为0），通讯网络有M条单向通讯线路，每条线路有一个固定的通讯花费Ci。

为了保密，消息的传递只能按照固定的方式进行：从一个已知消息的部门向另一个与它有线路的部门传递（可能存在多条通信线路）。我们定义总费用为所有部门传递消息的费用和。

幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方法将信息由X传递到Y，同时能由Y传递到X），我们就可以忽略它们之间的花费。

由于资金问题（预算都花在粒子对撞机上了），SERN总部的工程师希望知道，达到目标的最小花费是多少。

输入格式

多组数据，文件以2个0结尾。

每组数据第一行，一个整数N，表示有N个包括总部的部门（从0开始编号）。然后是一个整数M，表示有M条单向通讯线路。

接下来M行，每行三个整数,Xi,Yi,Ci，表示第i条线路从Xi连向Yi，花费为 Ci。

输出格式

每组数据一行，一个整数表示达到目标的最小花费。

样例

样例输入

样例输出

数据范围与提示

样例解释

第一组数据：总部把消息传给分部1，分部1再传给分部2.总费用：100+50=150.

第二组数据：总部把消息传给分部1，由于分部1和分部2可以互相传递消息，所以分部1可以无费用把消息传给2.总费用：100+0=100.

第三组数据：总部把消息传给分部1，最小费用为50.总费用：50.

数据范围

对于10%的数据，保证M=N-1

对于另30%的数据，N ≤ 20 ，M ≤ 20

对于100%的数据，N ≤ 50000 ，M ≤ 10^5 ，Ci ≤ 10^5 ，

数据组数 ≤ 5
数据保证一定可以将信息传递到所有部门。

考虑到题解太短所以把题面粘上了……

大水题一个（然而居然没有一眼看出……），首先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:\n",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\n",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\n",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;

}

巴特西

HZOJ 通讯