hdu 1827
Tarjan + 缩点
题意：Wiskey知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到（通知的人最少花费也就会最小）。
思路:缩点（缩点就是用强连通分量中的一个点代替其余的点）之后有几个入度为0的就要通知几次，然后在那个强连通分量里找最便宜的打过去（强连通分量中的最小花费可以在Tarjan算法中预处理一下）。
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005,maxm=2005;
int cnt;//强连通分量（SCC）的个数
int low[maxn],num[maxn],dfn;
int sccno[maxn],zhan[maxn],top;
int head[maxn],Next[maxm],to[maxm],tot;
int val[maxn],cost[maxn],du[maxn];
struct node{
int u,v;
}pos[maxm];
inline void add(int u,int v) {
to[tot]=v;
Next[tot]=head[u];
head[u]=tot;
}
void dfs(int u) {
zhan[top++]=u;
low[u]=num[u]=++dfn;
for(int i=head[u];i;i=Next[i]) {
int v=to[i];
if(!num[v]) {
dfs(v);
low[u]=min(low[v],low[u]);
}
else if(!sccno[v])
low[u]=min(low[u],num[v]);
}
if(low[u]==num[u]) {
++cnt; int mincost=0x3f3f3f3f;
while(1){
int v=zhan[--top];
sccno[v]=cnt;
mincost=min(mincost,val[v]);
if(u==v) break;
}
cost[cnt]=mincost;
}
}
void Tarjan(int n) {
cnt=top=dfn=0;
fill(sccno,sccno+maxn,0);
fill(num,num+maxn,0);
fill(low,low+maxn,0);
for(int i=1;i<=n;++i) if(!num[i])
dfs(i);
}
int main() {
int n,m,u,v;
while(~scanf("%d%d",&n,&m)) {
fill(head,head+maxn,0);
fill(du,du+maxn,0);
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
for( tot=1;tot<=m;++tot ) {
scanf("%d%d",&pos[tot].u,&pos[tot].v);
add(pos[tot].u,pos[tot].v);
}
Tarjan(n);
for(int i=1;i<=m;++i) {
int u=pos[i].u,v=pos[i].v;
if(sccno[u]==sccno[v]) continue;
else ++du[sccno[v]];
}
int ans1=0,ans2=0;
for(int i=1;i<=cnt;++i) if(!du[i]){
++ans1;
ans2+=cost[i];
}
printf("%d %d\n",ans1,ans2);
}
return 0;
} hdu 3072
题意：给你一个有向网络,网络中的每条有向边都有一个代价,表示从u向v发信息的代价.现在你要从0号点将信息发到所有的其他点去,问你最小代价是多少.其中如果u与v点可以互达(即属于同一个强连通分量),那么他们之间的通信不需要花代价. 输入保证从0号点能到达所有其他点。
思路：求出所有的强连通分量，然后将其缩点，因为是张连通图，所以只要求出每个强连通分量被通知的最小价值，然后累加即可。有点像最小生成树，但不完全是，假设求出了三个强连通分量了，分别标号为1，2，3
再给出边 1-->2，权值1，边1-->3权值5，边3-->2权值4 。按最小生成树的话，得到的结果是5，然而应该是6。求出每个强连通分量被通知的最小价值可以通过用缩点重建一张有向图来求，也可以直接求。
最重要的就是：紫书的板子有些地方比较多余，其实low数组可以不初始化的，还有low数组和sccno数组的功能有点重和，让我一开始误以为low记录的是某个点属于的强连通分量，但low在这里只起到了判断是否有重边的作用，sccno记录的才是某个点属于的强连通分量，别人的模板两个数组的作用刚好反了过来，因为一开始是复制他的代码，没注意到这个问题，逻辑上是没有问题的，一直wa，debug了8个多小时才发现，当然别人的模板更简洁更直接，看了一眼就能分清两个数组的区别，而且只需要初始化一个数组，虽然紫书的模板不是很好，但是在更新的时候会更理解模板的含义。还有的就是我复制了两个dfs，一个dfs改成dfs2，然后忘记调用，再然后里面的dfs忘记改成dfs2，，QAQ
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=50005,maxm=100005;
int cnt;
int low[maxn],num[maxn],dfn;
int sccno[maxn],zhan[maxn],top;
int head[maxn],Next[maxm],to[maxm],val[maxm],tot;
struct node{
int u,v;
}pos[maxm];
inline void add(int u,int v,int w) {
to[tot]=v;
val[tot]=w;
Next[tot]=head[u];
head[u]=tot;
}
void dfs(int u) {
zhan[top++]=u;//u进栈
low[u]=num[u]=++dfn;
for(int i=head[u];~i;i=Next[i]) {
int v=to[i];
if(!num[v]) {
dfs(v);//访问到DFS的最后一层，是最后一个SCC，或者是一个SCC的最后一个元素
low[u]=min(low[v],low[u]);//他可能有多个儿子，儿子如果和它不是一个SCC，
//只有儿子和它是一个SCC，low[v]才会小于等于low[u]
}//为访问过的点，继续DFS
else if(!sccno[v])
low[u]=min(low[u],num[v]);
//访问过的点可能是已经处理过的SCC上的点(还可能有重边)
}
if(low[u]==num[u]) {
++cnt;
while(1){
int v=zhan[--top];
sccno[v]=cnt;
if(u==v) break;//栈底的点是SCC的祖先，它low[u]==num[u]
}
}
}
void Tarjan(int n) {
cnt=top=dfn=0;
fill(sccno,sccno+maxn,0);
fill(num,num+maxn,0);
for(int i=0;i<n;++i) if(!num[i])
dfs(i);
}
int dp[maxn],du[maxn];
void dfs2(int u){
if(num[u])return;
num[u]=1;
for(int i=head[u];~i;i=Next[i]){
int v=to[i],w=val[i];
if(w<dp[v]) dp[v]=w;
dfs2(v);
}
}
int main() {
int n,m,w;
while(~scanf("%d%d",&n,&m)) {
fill(head,head+maxn,-1);
for( tot=1;tot<=m;++tot ) {
scanf("%d%d%d",&pos[tot].u,&pos[tot].v,&w);
add(pos[tot].u,pos[tot].v,w);
}
Tarjan(n);
fill(dp,dp+maxn,1e9);
for(int u=0;u<n;u++)
for(int i=head[u];~i;i=Next[i]) {
int v=to[i];
int x=sccno[u], y=sccno[v];
if(x!=y) dp[y]=min(dp[y],val[i]);
}
int ans=0;
for(int i=1;i<=cnt;i++)if(i!=sccno[0])
ans+= dp[i];
printf("%d\n",ans);
}
return 0;
}
更新后的模板：
#include<bits/stdc++.h>
using namespace std;
const int maxn=50005,maxm=100005;
int cnt;
int low[maxn],num[maxn],dfn;
int sccno[maxn],zhan[maxn],top;
int head[maxn],Next[maxm],to[maxm],val[maxm],tot;
struct node{
int u,v;
}pos[maxm];
inline void add(int u,int v,int w) {
to[tot]=v;
val[tot]=w;
Next[tot]=head[u];
head[u]=tot;
}
void Tarjan(int u) {
if(sccno[u]) return;
zhan[top++]=u;//u进栈
low[u]=num[u]=++dfn;
sccno[u]=1;
for(int i=head[u];~i;i=Next[i]) {
int v=to[i];
Tarjan(v);
if(sccno[v]==1)
low[u]=min(low[u],low[v]);
}
if(low[u]==num[u]) while(1){
int v=zhan[--top];
sccno[v]=-1;
low[v]=low[u];
if(u==v) break;
}
}
int dp[maxn];
void dfs2(int u){
if(num[u])return;
num[u]=1;
for(int i=head[u];~i;i=Next[i]){
int v=to[i],w=val[i];
if(w<dp[v]) dp[v]=w;
dfs2(v);
}
}
int main() {
int n,m,w;
while(~scanf("%d%d",&n,&m)) {
fill(head,head+maxn,-1);
for( tot=1;tot<=m;++tot ) {
scanf("%d%d%d",&pos[tot].u,&pos[tot].v,&w);
add(pos[tot].u,pos[tot].v,w);
}
top=dfn=0;
fill(sccno,sccno+maxn,0);
for(int i=0;i<n;++i) if(!sccno[i])
Tarjan(i);
fill(dp,dp+maxn,1e9);
for(int u=0;u<n;u++)
for(int i=head[u];~i;i=Next[i]) {
int v=to[i];
int x=low[u], y=low[v];
if(x!=y) dp[y]=min(dp[y],val[i]);
}
int ans=0; dp[low[0]]=0;
for(int i=1;i<n;++i) {
ans+= dp[low[i]];
dp[low[i]]=0;
}
printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号