【poj1236】 Network of Schools

时间：2023-03-08 22:24:43

http://poj.org/problem?id=1236 (题目链接)

题意

　　给定一个有向图，求：1．至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点；２．至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点。

Solution

　　先用Tarjan缩点，所以原图就变成了一个有向无环图（DAG），问题1很简单，只要找出图中入度为0的点有几个就可以了。而第2问的话，看起来就觉得好麻烦的样子，可是看了题解后发现原来如此简单。。用ans1记录入度为0的点的个数，ans2记录出度为0的点的个数，让当前点形成连通块的条件是什么呢，所有的点的入度和出度都不为0。将出度为0的点连一条边向入度为0的点，如果还有多余，那么随意向其他点连边即可，所以第二问的答案就是max（ans1，ans2）。当缩点后只有一个点的话，那么就直接输出1和0。

代码

// poj2186

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=2000;

struct edge {int to,next;}e[maxn<<2],ee[maxn<<2];

int s[maxn],dfn[maxn],low[maxn],head[maxn],heade[maxn],f[maxn],r[maxn],c[maxn],pos[maxn],b[maxn][maxn];

int cnt,top,tot,n,ind;

void insert(int u,int v) {

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

}

void inserte(int u,int v) {

    ee[++cnt].to=v;ee[cnt].next=heade[u];heade[u]=cnt;

}

void Tarjan(int u) {

    dfn[u]=low[u]=++ind;

    s[++top]=u;

    f[u]=1;

    for (int i=head[u];i;i=e[i].next) {

        if (!dfn[e[i].to]) {

            Tarjan(e[i].to);

            low[u]=min(low[u],low[e[i].to]);

        }

        else if (f[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);

    }

    if (low[u]==dfn[u]) {

        tot++;int j;

        do {

            j=s[top--];

            pos[j]=tot;

            f[j]=0;

        }while (j!=u);

    }

}

int main() {

    while (scanf("%d",&n)!=EOF) {

        ind=0;cnt=0;top=0;

        for (int i=1;i<=n;i++) pos[i]=heade[i]=head[i]=s[i]=dfn[i]=low[i]=r[i]=c[i]=0;

        for (int i=1;i<=n;i++) {

            int x;

            while (scanf("%d",&x)!=EOF && x!=0) insert(i,x);

        }

        for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);

        cnt=0;

        for (int i=1;i<=n;i++)

            for (int j=head[i];j;j=e[j].next)

                if (!b[pos[i]][pos[e[j].to]] && pos[i]!=pos[e[j].to])

                    inserte(pos[i],pos[e[j].to]);

        for (int i=1;i<=tot;i++)

            for (int j=heade[i];j;j=ee[j].next) {

                r[ee[j].to]++;

                c[i]++;

            }

        int ans1=0,ans2=0;

        for (int i=1;i<=tot;i++) if (r[i]==0) ans1++;

        for (int i=1;i<=tot;i++) if (c[i]==0) ans2++;

        printf("%d\n",ans1);

        if (tot==1) printf("0\n");

        else printf("%d\n",max(ans1,ans2));

    }

    return 0;

}

　　

相关文章