洛谷—— P2812 高校网络

7. 通讯线路

★★   输入文件:mcst.in   输出文件:mcst.out   不难相比较
光阴限制:1.5 s   内存限制:128 MB

难点讲述

只要要在n个城市里面确立通讯联络网,则连通n个城市只供给n-1条线路。那时,
怎么样在至少经费的前提下树立那几个通信网。在每多个都市里面都能够设置—条线路,相应地都要交给一定的经济代价。n个城市里面,最多大概设置n(n-
1)/2条路线,那么,怎么着在那一个恐怕的线路中选拔n-1条,以使总的费用最少呢?

 

【输入格式】

输入文件有好多行
首先行,二个平头n,表示共有n个城市
第①–n+1行,每行n个数,分别表示该城市与别的城市里面路线的开销,要是城市间不可能树立通讯则用-1象征

 

【输出格式】

一行,3个整数,表示最少总开销

 

【输入输出样例】

 

输入文件

 


-1 5 -1 -1 -1 -1 
5 -1 50 -1 -1 10
-1 50 -1 20 10 -1
-1 -1 20 -1 60 30
-1 -1 10 60 -1 100
-1 10 -1 30 100 -1

 

出口文件

 

75

 

【数据规模】

 

对于40%的数据,保证有n<100: 
对于60%的数据,保证有n<256; 
对于整个的数额,保证有n<=1501。

 

 

复习一下最小生成树

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5000000
using namespace std;
int n,x,y,z,tot,ans,sum,fa[N];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;    
}
struct Edge
{
    int x,y,z;
}edge[N];
int cmp(Edge a,Edge b)
{
    return a.z<b.z;
}
int find(int x)
{
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    freopen("mcst.in","r",stdin);
    freopen("mcst.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
    {
        z=read();
        if(z==-1) continue;
        tot++;
        edge[tot].x=i;
        edge[tot].y=j;
        edge[tot].z=z;
    }
    sort(edge+1,edge+1+tot,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=tot;i++)
    {
        x=edge[i].x,y=edge[i].y;
        int fx=find(x),fy=find(y);
        if(fx==fy) continue;
        fa[fx]=fy;ans+=edge[i].z;
        sum++;
        if(sum==n-1) break;
    }
    printf("%d",ans);
    return 0;
}

 

 P2812 学校互联网

难点背景

青海省的几所OI强校的神犇发明了一种人工智能,能够AC任何难题,所以她们操纵建立一个网络来共享那几个软件。可是出于她们头脑劳动过多导致全身无力身体被♂掏♂空,他们来找你扶助她们。

题目叙述

共有n所高校(n<=一千0)已知他们落到实处设计好的互连网共m条线路,为了保险高速,网络是单向的。现在请您告知她们足足选几所高校作为共享软件的母机母鸡,能使每所学院和学校都能够用上。再告诉他们至少要添加几条线路能使任意一所学院和学校作为母机母鸡都得以使别的高校利用上软件。

输入输出格式

输入格式:

 

先是行2个平头n。

接下去n行每行有几个整数,用空格空格隔开分离。

第i-1行的非零整数x,表示从i到x有一条线路。以0作为完成标志。

 

输出格式:

 

率先行一个整数表示难点1的答案。

第一行回答难点2.

 

输入输出样例

输入样例#1:

5
2 0
4 0
5 0
1 0
0

输出样例#1:

2
2

说明

POJ原题。数据扩张了100倍。

 

tarjan求强连通分量水题

求出强连通分量未来,大家知晓入度为零的点正是无音信来自的点。

强连通分量满足该强连通分量中无入度为零的点以及出度为零的点,那么我们要添加的边的条数正是max(入度为零的点的个数,出度为零的点的个数)

代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100000
using namespace std;
bool vis[N];
int n,x,top,tim,tot,sum,ans,ans1,ans2;
int in[N],out[N],dfn[N],low[N],head[N],stack[N],belong[N];
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct Edge
{
    int from,to,next;
}edge[N];
int add(int x,int y)
{
    tot++;
    edge[tot].to=y;
    edge[tot].next=head[x];
    head[x]=tot;
}
int tarjan(int now)
{
    dfn[now]=low[now]=++tim;
    stack[++top]=now;vis[now]=true;
    for(int i=head[now];i;i=edge[i].next)
    {
        int t=edge[i].to;
        if(vis[t]) low[now]=min(low[now],dfn[t]);
        else if(!dfn[t]) tarjan(t),low[now]=min(low[now],low[t]);
    }
    if(low[now]==dfn[now])
    {
        sum++,belong[now]=sum;
        for(;stack[top]!=now;top--)
        {
            int t=stack[top];
            belong[t]=sum,vis[t]=false;
        }
        vis[now]=false; top--;
    }
}
int shink_point()
{
    for(int i=1;i<=n;i++)
     for(int j=head[i];j;j=edge[j].next)
     {
         int t=edge[j].to;
         if(belong[i]!=belong[t]) 
          in[belong[t]]++,out[belong[i]]++;
     }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            x=read();
            if(x==0) break;
            add(i,x);
        }
    }  
    for(int i=1;i<=n;i++)
     if(!dfn[i]) tarjan(i);
    shink_point();
    for(int i=1;i<=sum;i++)
    {
        if(in[i]==0) ans1++;
        if(out[i]==0) ans2++;
     } 
    ans=max(ans1,ans2);
    printf("%d\n%d\n",ans1,ans);
    return 0;
}