POJ 3275

1583 ワード

FLOYDの隣接表形式
この問題の難解な点は,どのくらいのペアの関係がC(N,2)−K(Nは点数,Kは明らかな関係ペア)に等しいかを調べる必要があるかということである.

#include
#include
#include
#include
#include
#include
#define N 1010
#define M 10100
typedef long long ll;
using namespace std;

struct Edge{
    int u,v,next;
}edge[N*N*2];
int head1[N],head2[N],p;//head1  ，head2  
int dis[N][N];

void addedge1(int u,int v){
    edge[p].u=u;
    edge[p].v=v;
    edge[p].next=head1[u];
    head1[u]=p++;
}
void addedge2(int u,int v){
    edge[p].u=u;
    edge[p].v=v;
    edge[p].next=head2[u];
    head2[u]=p++;
}
void init(){
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    memset(dis,0,sizeof(dis));
    p=0;
}
int main(){
    int i,j,k,n,m;
    int u,v;
    scanf("%d %d",&n,&m);
    init();
    for(i=1;i<=m;i++){
        scanf("%d %d",&u,&v);
        dis[u][v]=1;
        addedge1(u,v);
        addedge2(v,u);
    }
    for(j=1;j<=n;j++)
        for(i=head1[j];i!=-1;i=edge[i].next){
            v=edge[i].v;
            for(k=head2[j];k!=-1;k=edge[k].next){
                u=edge[k].v;
                if(dis[u][v]==0){
                    dis[u][v]=1;
                    addedge1(u,v);
                    addedge2(v,u);//     
                }
            }
        }
    int ans=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(dis[i][j]==1)
                ans++;
    printf("%d
",n*(n-1)/2-ans);
    return 0;
}

クッキーのSecureフラグはリバースプロキシに立てさせたい

CentOs 7ヒントパッケージdockerをインストールしていない解決方法