TOJ 3365 ZOJ 3232 It's not Floyd Algorithm / 强连通分量 - c++编程基础

TOP

TOJ 3365 ZOJ 3232 It's not Floyd Algorithm / 强连通分量

2015-11-21 01:56:04 来源: 作者: 【大中小】浏览:6次

Tags：TOJ 3365 ZOJ 3232 It' not Floyd Algorithm 连通分量

It's not Floyd Algorithm

时间限制(普通/ Java):1000MS/3000MS ? ? 运行内存限制:65536KByte

描述

When a directed graph is given, we can solve its transitive closure easily using the well-known Floyd algorithm.

But if you're given a transitive closure, can you give a corresponding directed graph with minimal edges?

输入

About 100 test cases, seperated by blank line.

First line of each case is an integer N (1<=N<=200). The followingN lines represent the given transitive closure in 0-1 matrix form, each line hasN numbers.

输出

For each case, just output the number of minimal edges of a directed graph which has a given transitive closure.

样例输入

1 0

0 1

1 1

1 1 1

0 1 1

0 0 1

样例输出

提示

Transitive closure can be presented as a matrix T, where Ti,j is true if and only if there is a path from vertexi toj.

首先缩点在建图对于每个强连通分量如果有n个点那么最少只需n条边就可以联通（n = 1 除外）

然后对于缩点后的图咋做一次反闭包去掉多余的边在统计一下

      
#include  
#include  
int n;  
int dfn[210];  
int low[210];  
bool instack[210];  
int stack[210];  
int cnt,num,top;  
int a[210][210];  
int count[210];  
int belong[210];  
int map[210][210];  
void floyd()  
{  
    int i,j,k;  
    for(k = 1;k <= cnt; k++)  
        for(i = 1;i <= cnt; i++)  
            for(j = 1;j <= cnt; j++)  
                if(map[i][k] && map[k][j] && map[i][j])  
                    map[i][j] = 0;  
}  
void tarjan(int i)  
{  
        int j,k;  
        dfn[i] = low[i] = ++num;  
        instack[i] = true;  
        stack[++top] = i;  
        for(j = 1;j <= n; j++)  
        {  
            k = a[i][j];  
            if(!k)  
                continue;  
            if(!dfn[j])  
            {  
                tarjan(j);  
                if(low[i] > low[j])  
                    low[i] = low[j];  
            }  
            else if(instack[j] && low[i] > dfn[j])  
                low[i] = dfn[j];  
        }   
        if(low[i] == dfn[i])  
        {  
            cnt++;  
            do  
            {  
                j = stack[top--];  
                instack[j] = false;  
                belong[j] = cnt;   
                count[cnt]++;  
            }  
            while(i != j);  
        }  
}   
int main()  
{  
    int i,j,sum;  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(i = 1;i <= n; i++)  
            for(j = 1; j<= n; j++)  
                scanf("%d",&a[i][j]);  
        num = top = cnt = 0;  
        memset(dfn,0,sizeof(dfn));  
        memset(instack,false,sizeof(instack));  
        memset(count,0,sizeof(count));  
        memset(map,0,sizeof(map));  
        for(i = 1;i <= n; i++)  
            if(!dfn[i])  
                tarjan(i);  
        for(i = 1; i<= n; i++)  
            for(j = 1; j<= n; j++)  
                if(a[i][j])  
                    if(belong[i] != belong[j])  
                        map[belong[i]][belong[j]] = 1;  
        sum = 0;  
        floyd();  
        for(i = 1;i <= cnt; i++)  
            if(count[i] != 1)  
                sum += count[i];  
        for(i = 1;i <= cnt; i++)  
            for(j = 1; j<= cnt; j++)  
                if(map[i][j])  
                    sum++;  
        printf("%d\n",sum);  
    }  
    return 0;  
}

? ?It's not Floyd Algorithm

时间限制(普通/Java):1000MS/3000MS ? ? 运行内存限制:65536KByte

描述