hdoj 3072 Intelligence System【求scc&&缩点】【求连通所有scc的最小花费】

时间:2022-09-06 11:57:38

Intelligence System

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1904    Accepted Submission(s): 824

Problem Description
After a day, ALPCs finally complete their ultimate intelligence system, the purpose of it is of course for ACM ... ... 
Now, kzc_tc, the head of the Intelligence Department (his code is once 48, but now 0), is sudden obtaining important information from one Intelligence personnel. That relates to the strategic direction and future development of the situation of ALPC. So it need for emergency notification to all Intelligence personnel, he decides to use the intelligence system (kzc_tc inform one, and the one inform other one or more, and so on. Finally the information is known to all).
We know this is a dangerous work. Each transmission of the information can only be made through a fixed approach, from a fixed person to another fixed, and cannot be exchanged, but between two persons may have more than one way for transferring. Each act of the transmission cost Ci (1 <= Ci <= 100000), the total cost of the transmission if inform some ones in our ALPC intelligence agency is their costs sum. 
Something good, if two people can inform each other, directly or indirectly through someone else, then they belong to the same branch (kzc_tc is in one branch, too!). This case, it’s very easy to inform each other, so that the cost between persons in the same branch will be ignored. The number of branch in intelligence agency is no more than one hundred.
As a result of the current tensions of ALPC’s funds, kzc_tc now has all relationships in his Intelligence system, and he want to write a program to achieve the minimum cost to ensure that everyone knows this intelligence.
It's really annoying!
 
Input
There are several test cases. 
In each case, the first line is an Integer N (0< N <= 50000), the number of the intelligence personnel including kzc_tc. Their code is numbered from 0 to N-1. And then M (0<= M <= 100000), the number of the transmission approach.
The next M lines, each line contains three integers, X, Y and C means person X transfer information to person Y cost C. 
 
Output
The minimum total cost for inform everyone.
Believe kzc_tc’s working! There always is a way for him to communicate with all other intelligence personnel.
 
Sample Input
3 3
0 1 100
1 2 50
0 2 100
3 3
0 1 100
1 2 50
2 1 100
2 2
0 1 50
0 1 100
 
Sample Output
150
100
50

题意:有N个人编号从0到N-1,给出M组关系<u,v,w>表示u联系v需要费用w(但不代表v联系u需要费用w)。若一个集合中 任意两个人可以互相联系(不管是直接联系的还是通过其他人间接联系的),那么在这个集合里面联系的费用可以忽略。现在你是编号0,问你联系到所有人的最小费用。题目保证至少有一组方案使得你可以联系到所有人。

题解:求出所有的scc,因为同一个scc中的人相互通知不需要花费,所以总花费是连接所有scc的花费

在缩点的过程同时更新连接scc所需要的最小花费   最后累加即可

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
#define MAX 100010
#define INF 0x3f3f3f
#include<vector>
using namespace std;
int n,m;
int head[MAX],ans;
int low[MAX],dfn[MAX];
int sccno[MAX];
int scccnt,dfsclock;
vector<int>scc[MAX];
vector<int>newmap[MAX];
stack<int>s;
int instack[MAX],money[MAX];
struct node
{
int beg,end,next;
int cost;
}edge[MAX];
void init()
{
ans=0;
memset(head,-1,sizeof(head));
}
void add(int beg,int end,int cost)
{
edge[ans].beg=beg;
edge[ans].end=end;
edge[ans].cost=cost;
edge[ans].next=head[beg];
head[beg]=ans++;
}
void getmap()
{
int a,b,c,i;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
}
void tarjan(int u)
{
int i,v;
s.push(u);
instack[u]=1;
low[u]=dfn[u]=++dfsclock;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].end;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scccnt++;
while(1)
{
v=s.top();
s.pop();
instack[v]=0;
sccno[v]=scccnt;
if(v==u)
break;
}
}
}
void find(int l,int r)
{
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(instack,0,sizeof(instack));
memset(sccno,0,sizeof(sccno));
dfsclock=scccnt=0;
for(int i=l;i<=r;i++)
{
if(!dfn[i])
tarjan(i);
}
}
void suodian()
{
int i;
for(i=1;i<=scccnt;i++)
{
newmap[i].clear();
money[i]=INF;
}
for(i=0;i<ans;i++)
{
int u=sccno[edge[i].beg];
int v=sccno[edge[i].end];
if(u!=v)//u不等于v证明u和v不在同一个scc,则u-->v这条边是连接两个scc的边,
{ //拿这条边和其他的可以连接这两个scc的边比较取最小值
newmap[u].push_back(v);
money[v]=min(edge[i].cost,money[v]);
}
}
}
void solve()
{
int i,j;
int sum=0;
for(i=1;i<=scccnt;i++)
{
if(sccno[0]!=i)//0所在的scc不需要花费,因为消息就是从这里来的
sum+=money[i];
}
printf("%d\n",sum);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
getmap();
find(0,n-1);
suodian();
solve();
}
return 0;
}

  

hdoj 3072 Intelligence System【求scc&&缩点】【求连通所有scc的最小花费】的更多相关文章

  1. HDU 3072 Intelligence System(tarjan染色缩点&plus;贪心&plus;最小树形图)

    Intelligence System Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe ...

  2. hdu 3072 Intelligence System&lpar;Tarjan 求连通块间最小值&rpar;

    Intelligence System Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other) ...

  3. HDU 3072 Intelligence System (强连通分量)

    Intelligence System Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe ...

  4. HDU——3072 Intelligence System

    Intelligence System Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe ...

  5. HDU——T 3072 Intelligence System

    http://acm.hdu.edu.cn/showproblem.php?pid=3072 Time Limit: 2000/1000 MS (Java/Others)    Memory Limi ...

  6. HDU - 3072 Intelligence System

    题意: 给出一个N个节点的有向图.图中任意两点进行通信的代价为路径上的边权和.如果两个点能互相到达那么代价为0.问从点0开始向其余所有点通信的最小代价和.保证能向所有点通信. 题解: 求出所有的强连通 ...

  7. Intelligence System &lpar;hdu 3072 强联通缩点&plus;贪心&rpar;

    Intelligence System Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe ...

  8. HDU 3072--Intelligence System【SCC缩点新构图 &amp&semi;amp&semi;&amp&semi;amp&semi; 求连通全部SCC的最小费用】

    Intelligence System Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe ...

  9. HDU 3072 SCC Intelligence System

    给出一个带权有向图,要使整个图连通.SCC中的点之间花费为0,所以就先缩点,然后缩点后两点之间的权值为最小边的权值,把这些权值累加起来就是答案. #include <iostream> # ...

随机推荐

  1. Uri各个属性取值测试

    asp.net代码: Uri h_uri = new Uri("http://hovertree.com/tiku/bjaf/3ntux9r9.htm?hewenqi#hewenqipl?d ...

  2. SpringMVC数据绑定全面示例(复杂对象,数组等)

    点击链接查询原文 http://www.xdemo.org/springmvc-data-bind/ 已经使用SpringMVC开发了几个项目,平时也有不少朋友问我数据怎么传输,怎么绑定之类的话题,今 ...

  3. 如何设计和实现一个web app

    web app简介 web app其实不算是什么新鲜的东西,相比于传统的web和传统的app,web app这种web和app相结合的产物有的优点如下: 1. 开发上web app更有便捷性,ios开 ...

  4. Oracle 唯一 约束(unique constraint) 与 索引(index) 关系说明

    一. 官网对Unique Constraints说明 http://download.oracle.com/docs/cd/E11882_01/server.112/e16508/datainte.h ...

  5. js格式化时间

    转自:https://blog.csdn.net/u010964869/article/details/51095827 显示格式为:yyyy-mm-dd hh:mi:ss function form ...

  6. linux强制拷贝避免输入yes方法

    Linux下默认cp命令是有别名(alias cp='cp -i')的,无法强制覆盖,即使你用 -f 参数也无法强制覆盖文件,下面提供两种Linux下cp 覆盖方法. 1) 取消cp的alias,这不 ...

  7. pch文件配置

    配置.pch文件 刚上手 Xcode6 的人,总会发现之前在 6 之前常常会在“利用名-Prefix.pch”这个文件中来配置我们全局要用到的头文件,但是 xcode6 没有了,人家说,这类东西有时候 ...

  8. C&plus;&plus;设计模式&lpar;转&rpar;

    在简书看到CharlesW同学学习设计模式的笔记,感觉很有意思(单身狗的妄想),转载下. 转载:https://www.jianshu.com/p/082662126bdd 好的软件设计是多用代码复用 ...

  9. linux大全链接

    http://man.linuxde.net/

  10. Iterable,Iterator和forEach

    Iterable Interface Iterable<T> 方法: Iterator<T> iterator() Returns an iterator over a set ...