题面
题解
- 一个博客
- 一点注释：那其实而更应称作bfs。然后那个(d_{i,0})和(d_{i,1})可以按照次短路的写法来理解
- 一点注意点：次短路出去了，就不要再经过与当前作为bfs的根节点距离为1的点了。
- 其实次短路的来源完全可以不用记录。
代码
#include<bits/stdc++.h>
#define LL long long
#define MAXN 2000
#define MAXM 50000
using namespace std;
template<typename T>void Read(T &cn)
{
char c;int sig = 1;
while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
while(isdigit(c = getchar()))cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
struct qwe{
int a,b,ne;
void mk(int cn, int cm, int cx) {a = cn; b = cm; ne = cx; }
};
qwe a[MAXM*2+1];
int alen;
int head[MAXN+1];
int tu[MAXN+1][MAXN+1];
int n,m;
int ge[MAXN+1][MAXN+1];
int ju[MAXN+1][2];
int lai[MAXN+1][2];
int ans[MAXN+1];
int dui[MAXN*2+1];
int zai[MAXN+1];
void lian(int cn, int cm) {a[++alen].mk(cn, cm, head[cn]); head[cn] = alen; tu[cn][cm] = 1; }
void shu_ge()
{
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) ge[i][j] = 0;
for(int i = 1;i<=alen;i++)
{
for(int j = 1;j<=n;j++) if(tu[a[i].b][j]) ge[a[i].a][j]++, ge[j][a[i].a]++;
}
}
int jian(int cn)
{
int guo = 0;
for(int i = 1;i<=n;i++) if(ge[cn][i] == 2 && !tu[cn][i] && cn != i) guo++;
return guo;
}
void nong(int cn)
{
// printf("in nong : cn = %d
",cn);
int l = 0, r = 0;
for(int i = 1;i<=n;i++) ju[i][0] = ju[i][1] = n+1, lai[cn][0] = lai[cn][1] = -1;
ju[cn][0] = ju[cn][1] = 0; lai[cn][0] = lai[cn][1] = 0;
for(int i = head[cn];i;i = a[i].ne) ju[a[i].b][1] = 1, lai[a[i].b][1] = a[i].b, dui[++r] = a[i].b*2+1;
while(l < r)
{
int dang = dui[++l];
int dang1 = dang/2, dang2 = dang%2;
for(int i = head[dang1];i;i = a[i].ne)
{
int y = a[i].b;
if(ju[y][1] > ju[dang1][dang2]+1) {ju[y][1] = ju[dang1][dang2]+1; dui[++r] = y*2+1; lai[y][1] = lai[dang1][dang2]; }
else if(ju[y][0] > ju[dang1][dang2]+1 && ju[y][1] != 1 && lai[y][1]!=lai[dang1][dang2]) {ju[y][0] = ju[dang1][dang2]+1; dui[++r] = y*2+0; lai[y][0] = lai[dang1][dang2]; }
/* if(dang2 == 1) {
if(ju[y][1] > ju[dang1][1]+1) {ju[y][1] = ju[dang1][1]+1; dui[++r] = y*2+1; lai[y] = lai[dang1]; }
if(ju[y][0] > ju[dang1][1]+1 && lai[y]!=lai[dang1]) {ju[y][0] = ju[dang1][1]+1; dui[++r] = y*2+0; }
}
else{
if(ju[y][0] > ju[dang1][0]+1) {ju[y][0] = ju[dang1][0]+1; dui[++r] = y*2+0; }
}*/
}
}
}
int main()
{
freopen("hole.in","r",stdin);
freopen("hole.out","w",stdout);
Read(n); Read(m);
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) tu[i][j] = 0;
alen = 0; memset(head,0,sizeof(head));
for(int i = 1;i<=m;i++) {int bx,by; Read(bx); Read(by); lian(bx,by); lian(by,bx); }
shu_ge(); memset(ans,0,sizeof(ans));
for(int i = 1;i<=n;i++) if(jian(i))
{
nong(i);
for(int j = head[i];j;j = a[j].ne)
{
for(int k = 1;k<=n;k++) if(ju[k][1] == 2) ans[a[j].b] += (lai[k][1] == a[j].b ? ju[k][0] : ju[k][1]) - ju[k][1];
}
}
for(int i = 1;i<=n;i++) Write(ans[i]/2), puts("");
return 0;
}