[清橙A1364]社交网络结构洞【暴力】

【题目描述】

试题来源

　　清华大学2012年信息学优秀高中学子夏令营

问题描述

　　近日，社交网络研究的鼻祖Jon Kleinberg教授在清华大学给同学们带来了一个关于社交网络结构洞（Structural Hole）的主题演讲。对社交网络有着浓厚兴趣的小W也旁听了这次演讲。在演讲中Jon Kleinberg教授讲到社交网络结构洞是描述一个人在一个社交网络中重要程度的一个指标，那么如何定量地分析每一个人在社交网络的重要程度呢？
　　小W阅读很多参考文献，发现有一种通过计算社会关系跨度的方法。

　　【定义】社交网络用

表示一个社交网络，其中

是网络中人的集合，

是人与人之间的关系集合。
　　【定义】社交网络距离

和

两个人的社交网络距离

为

和

之间的最短距离。
　　【定义】社会关系跨度用

表示，是在社交网络中去掉所有与

相关的边（即边的一个端点为

）之后

和

之间的最短距离。
　　那么描述每一个人的结构洞值

表示其所有邻居节点之间社会关系跨度与社交网络距离差值的和。

　　(结构洞值的定义）

　　其中

表示

的邻居节点集合。
　　由于社交网络中人的数量十分庞大，计算每个人的结构洞值也变得十分困难。小W想请你帮助设计出一种好的计算方法，求出社交网络中所有人的结构洞值。

输入格式

　　输入的第一行包含两个整数n,m，表示社交网络中人的数量（人从1到n编号）和关系的数量。
　　接下来m行描述人们的关系情况，其中第i行包含两个整数a_i和b_i,1<=a_i,b_i<=n，表示a_i和b_i两个人之间在社交网络中有直接关系。

输出格式

　　输出一共n行，每行一个整数，表示每个人在社交网络中的结构洞值。

样例输入

样例输出

对样例的说明

数据规模和约定

　　所有测试数据的范围和特点如下表所示。

【题解】

不大会做，YY了一下感觉有用的点对数量很少，就写了一个暴力，bfs两步找出所有距离为2，且有唯一路径的点对，按经过

的那个点排序宽搜次短路，第一次60分，加了每次宽搜只搜完所有要用的点的优化就不明不白的A了。

正解好像是spfa求出次短路（出发后的第一个点与最短路不同），但与我的跑的差不多快。

# include <bits/stdc++.h>
# define    M       50010
# define    N       2010
# define    inf     1e9
using namespace std;
struct node{
    int data,next;
}e[M*2];
struct Q{
    int x,y,c;
}q[N*N];
int qu[N],n,dis[N],head[N],cut[N],m,place,tag[N],frm[N],num,ans[N],use[N],sum;
bool cmp(Q x, Q y){
    return x.x<y.x||x.x==y.x&&x.c<y.c;
}
void build(int u, int v){
    e[++place].data=v; e[place].next=head[u]; head[u]=place;
    e[++place].data=u; e[place].next=head[v]; head[v]=place;
}
int read(){
    int tmp=0,fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
void bfs(int x){
    for (int i=1; i<=n; i++) dis[i]=inf;
    int pl=1, pr=1; qu[1]=x; dis[x]=0;
    while (pl<=pr){
        int x=qu[pl++];
        for (register int ed=head[x]; ed!=0; ed=e[ed].next)
            if (dis[e[ed].data]==inf&&cut[e[ed].data]==false){
                dis[e[ed].data]=dis[x]+1;
                if (use[e[ed].data]==true){
                    use[e[ed].data]=0, sum--;
                    if (!sum) return;
                }
                qu[++pr]=e[ed].data;
            }
    }
}
int main(){
    n=read(); m=read();
    for (int i=1; i<=m; i++)
        build(read(),read());
    for (int i=1; i<=n; i++){
        memset(tag,0,sizeof(tag));
            for (int j=head[i]; j!=0; j=e[j].next){
            int x=e[j].data; tag[x]=-inf;
            for (int k=head[x]; k!=0; k=e[k].next)
                tag[e[k].data]++, frm[e[k].data]=x;
        }
        for (int j=i+1; j<=n; j++)
            if (tag[j]==1) {
                q[++num].x=i; q[num].y=j; q[num].c=frm[j];
            }
    }
    sort(q+1,q+num+1,cmp);
    for (register int i=1; i<=num;){
        int j=i;
        while (j<=num&&q[i].x==q[j].x&&q[i].c==q[j].c) j++;
        j--;
        cut[q[j].c]=true;
        sum=j-i+1;
        for (register int k=i; k<=j; k++) use[q[k].y]=true;
        bfs(q[i].x); 
        for (register int k=i; k<=j; k++) ans[q[k].c]+=dis[q[k].y]-2;
        i=j+1; cut[q[j].c]=false;
    }
    for (int i=1; i<=n; i++)
        printf("%d
",ans[i]);
    return 0;
}