【离散数学】 SDUT OJ 传递闭包 && memset 使用注意事项

传递闭包

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知有n头牛，m次战斗关系，询问最终可以确定排名的牛的数量。

Input

多组测试数据，对于每组测试数据，第1行输入两个整数n(1 <= n <= 100)和m(0 <= m <= 4950)，分别表示有n头牛和m次战斗关系，之后m行每行输入两个正整数x和y表示编号为x的牛可以战胜编号为y的牛，数据保证合法，询问可以确定排名的牛的数量。

Output

对于每组测试数据，输出整数ans，表示可以确定排名的牛的数量。

Sample Input

Sample Output

#include<stdio.h>
#include<string.h>
int a[110][110];
/*头天晚上老是WA，第二天一样的代码就A了，肯定又是OJ的数据出了问题，本地对了就是对了；
  Warshall算法不难写，计算牛的排名数量不太好想；
  懒，改天再写注释*/
void warshell(int n)
{
    //warshell算法；
    int k, i, j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(a[j][i])
            {
                for(k=1; k<=n; k++)
                {
                    a[j][k] = a[j][k] + a[i][k];
                    if(a[j][k] >= 1)
                        a[j][k] = 1;
                }
            }
        }
    }
}
int main()
{
    int m, n, x, y, i, j, ans, flag[110];
    while(~scanf("%d %d", &n, &m))
    {
        ans = 0;
        memset(a, 0, sizeof(a));
        memset(flag, 1, sizeof(flag));  //不建议对int类型用memset函数赋非零值;但这里只是做个标记，对结果没影响;
        while(m--)
        {
            scanf("%d %d", &x, &y);
            a[x][y] = 1;
        }
        warshell(n);
        for(j=1; j<=n; j++)
        {
            //确定排名需要两个条件;
            //这里的排名情况是这样：4→3→2→5;
            //                        ↑
            //                        1
            //warshell之后就增加了传递性的箭头;
            //用矩阵表示出来之后结合关系图就能看出两个条件了;
            //一是除了没有自回路(a[i][i]=0)和不对称(a[i][j]=0时a[j][i]=1);
            //二是这一列除了上面两个值是0外，其余全为1;
            //
            for(i=1; i<=n; i++)
            {
                if(i == j)
                {
                    if(a[i][j])
                    {
                        flag[j] = 0; //a[i][i] = 1(有自回路)时，作出标记直接退出;
                        break;
                    }
                }
                else if(!a[i][j])
                {
                    if(!a[j][i])    //对称的两个数全是0；作出标记直接退出 ；
                    {
                        flag[j] = 0;
                        break;
                    }
                }
            }
            if(flag[j])  //不能用flag[j] == 1 判断；
            {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
/***************************************************
User name: jk170414高金满
Result: Accepted
Take time: 0ms
Take Memory: 196KB
Submit time: 2018-04-13 12:19:25
****************************************************/

——————————————分割线——————————————

有了新收获：

memset部分注意事项：

memset是计算机中C/C++语言函数。将s所指向的某一块内存中的后n个字节的内容全部设置为ch指定的ASCII值，第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为s。
char a[5];
memset(a,'1',5）;

int a[5];
memset(a,1,20）;

第一个程序为什么可以，而第二个不行
第一个程序的数组a是字符型的，字符型占据内存大小是1Byte，而memset函数也是以字节为单位进行赋值的，所以输出是1没有问题。而第二个程序a是整型的，使用 memset还是按字节赋值，这样赋值完以后，每个数组元素的值实际上是0x01010101即十进制的16843009

如果用memset(a,1,20)，就是对a指向的内存的20个字节进行赋值，每个都用数1去填充，转为二进制后，1就是00000001，占一个字节。一个int元素是4字节，合一起是0000 0001,0000 0001,0000 0001,0000 0001，转化成十六进制就是0x01010101，就等于16843009，就完成了对一个int元素的赋值了

结论：

memset是对字节进行操作，而且用memset对非字符型数组赋非零初值是不可取的；

【离散数学】 SDUT OJ 传递闭包 && memset 使用注意事项

传递闭包

推荐阅读