poj 3275(bitset Floyd AC,邻接表解法还不会)

#include<iostream>
#include<cstring>
#include<bitset>
#include<cstdio>
using namespace std;
const int maxn = 1005;
bitset<maxn>data[maxn];
int n,m;
void floyd(){
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n;i++){
            if(data[i][j]==1){
                data[i]|=data[j];
            }
        }
    }
}
int main(){
    int i,j,a,b,ans;
    scanf("%d%d",&n,&m);
    memset(data,0,sizeof data);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        data[a][b] = 1;
    }
    floyd();
    ans = 0; 
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(data[i][j]==1){
                ans++;
            }
        }
    }
    cout<<n*(n-1)/2-ans<<endl;
    return 0;
}

 

上一篇:快乐的一天从AC开始 | 20210717 | 牛客小白月赛36J


下一篇:安卓 ADB常见问题整理