HDU 3072 Intelligence System(强连通分量)
http://acm.hdu.edu.cn/showproblem.php?pid=3072
题意:给你一个有向网络,网络中的每条有向边都有一个代价,表示从u向v发信息的代价.现在你要从0号点将信息发到所有的其他点去,问你最小代价是多少.其中如果u与v点可以互达(即属于同一个强连通分量),那么他们之间的通信不需要花代价. 输入保证从0号点能到达所有其他点.
分析:
注意,本题输入可能有重边.不过与无重边的情况没任何区别,不同特殊处理.
首先求出图的所有连通分量,然后缩点形成DAG新图.对于同一个分量来说,分量内的信息传递都是免费的,只有分量之间(即DAG图的点之间)传递信息需要花费代价. 且由于题意保证了每个点都可达,所以DAG图每个点(除了0号点所在分量形成的点)的入度都>=1.所以我们只需要用val[i]记录第i个分量的入边中代价最小的那个值即可.
然后我们把(除0号点所在分量的val值外)所有的点所在分量的val值加起来就是我们通信花费的总代价.
AC代码: (用vector做有点慢,用邻接边表做更快)
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=50000+10;
int n,m;
vector<int> G[maxn],cost[maxn];
stack<int> S;
int dfs_clock, scc_cnt;
int pre[maxn],low[maxn],sccno[maxn];
int val[maxn];//val[i]=x表第i个分量的入边中代价最小为x
void dfs(int u)
{
pre[u]=low[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!sccno[v])
low[u]=min(low[u],pre[v]);
}
if(low[u]==pre[u])
{
scc_cnt++;
while(true)
{
int x=S.top(); S.pop();
sccno[x]=scc_cnt;
if(x==u) break;
}
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
memset(pre,0,sizeof(pre));
memset(sccno,0,sizeof(sccno));
for(int i=0;i<n;i++)
if(!pre[i]) dfs(i);
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
for(int i=0;i<n;i++) G[i].clear(),cost[i].clear();
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(v);
cost[u].push_back(w);
}
find_scc(n);
for(int i=1;i<=scc_cnt;i++) val[i]=1e6;
for(int u=0;u<n;u++)
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
int x=sccno[u], y=sccno[v];
if(x!=y) val[y]=min(val[y],cost[u][i]);
}
int ans=0;
for(int i=1;i<=scc_cnt;i++)if(i!=sccno[0])
ans+= val[i];
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: AC code: /* Tarjan求有向图的强连通分量, */ #include #...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
Hdu 1237 解题代码