[loj3501]图函数

$f(i,G)_{x}$为$x$对$i$是否有贡献，即在枚举到$x$时，$i$与$x$是否强连通

事实上，$f(i,G)_{x}=1$即不经过$[1,x)$中的点且$i$与$x$强连通

首先，当存在这样的路径，即使$[1,x)$中的点全部删除两者也仍然强连通（有贡献）

同时，若不存在这样的路径，考虑任意两条$i$到$x$和$x$到$i$的路径$P_{1}$和$P_{2}$，对于$P_{1}$和$P_{2}$中编号最小的点$y$，即证明若$y<x$，则其在枚举到$x$时必然被删去

不妨假设$y$在$P_{1}$中，当枚举到$y$时显然存在走$P_{1}$从$i$到$y$的路径，以及$y$到$i$的路径（先走$P_{1}$从$y$到$i$，再走$P_{2}$从$x$到$i$），那么$y$即会被删除

综上，也就证明了前面的结论

考虑对于确定的$i$和$x$，满足$f(i,G_{j})_{x}=1$的$j$必然是一个前缀，下面求出这个前缀——

令$d(i,x,y)$表示从$i$到$x$不经过$[1,y]$的所有路径中，经过的编号最小值的最大值，那么这个前缀的范围即$[0,\min(d(i,x,x-1),d(x,i,x-1)))$，差分统计即可

（特别的，为了方便，定义$d(i,i,x)$为$m+1$）

下面考虑如何求出$d(i,x,y)$，显然其与最短路类似，且定义又与Floyd的过程相同，即从大到小枚举中转点来转移即可，复杂度为$o(n^{3}+m)$

也可以暴力计算，即枚举$x$并删去这些点，以$x$为起点对原图和反图分别求一次，同样可以用dijkstra等最短路算法，即可做到$o(nm\log n)$的复杂度

上述两种算法复杂度并不正确，但常数优秀都可以通过

下面给出两份被卡常数的代码，分别是44（Floyd）和80（Dijkstra）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 1005

 4 #define M 300005

 5 int n,m,x,y,tot[M],f[N][N];

 6 int main(){

 7     scanf("%d%d",&n,&m);

 8     memset(f,-1,sizeof(f));

 9     for(int i=1;i<=n;i++)f[i][i]=m+1;

10     for(int i=1;i<=m;i++){

11         scanf("%d%d",&x,&y);

12         f[x][y]=i;

13     }

14     for(int i=n;i;i--){

15         for(int j=1;j<=n;j++)

16             for(int k=1;k<=n;k++)

17                 if ((f[j][i]>0)&&(f[i][k]>0))f[j][k]=max(f[j][k],min(f[j][i],f[i][k]));

18         for(int j=i;j<=n;j++)

19             if ((f[i][j]>0)&&(f[j][i]>0))tot[min(f[i][j],f[j][i])-1]++;

20     }

21     for(int i=m;i;i--)tot[i-1]+=tot[i];

22     for(int i=0;i<=m;i++)printf("%d ",tot[i]);

23 }

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 1005

 4 #define M 200005

 5 struct Edge{

 6     int nex,to,len;

 7 }edge[M<<1];

 8 priority_queue<pair<int,int> >q;

 9 int E,n,m,x,y,head[2][N],d[2][N],vis[N],tot[M];

10 void add(int p,int x,int y,int z){

11     edge[E].nex=head[p][x];

12     edge[E].to=y;

13     edge[E].len=z;

14     head[p][x]=E++;

15 }

16 void calc(int p,int st){

17     memset(d[p],-1,sizeof(d[p]));

18     memset(vis,0,sizeof(vis));

19     d[p][st]=m+1;

20     q.push(make_pair(d[p][st],st));

21     while (!q.empty()){

22         int k=q.top().second;

23         q.pop();

24         if (vis[k])continue;

25         vis[k]=1;

26         for(int i=head[p][k];i!=-1;i=edge[i].nex)

27             if ((edge[i].to>=st)&&(d[p][edge[i].to]<min(d[p][k],edge[i].len))){

28                 d[p][edge[i].to]=min(d[p][k],edge[i].len);

29                 q.push(make_pair(d[p][edge[i].to],edge[i].to));

30             }

31     }

32 }

33 int main(){

34     scanf("%d%d",&n,&m);

35     memset(head,-1,sizeof(head));

36     for(int i=1;i<=m;i++){

37         scanf("%d%d",&x,&y);

38         add(0,x,y,i);

39         add(1,y,x,i);

40     }

41     for(int i=1;i<=n;i++){

42         calc(0,i),calc(1,i);

43         for(int j=i;j<=n;j++)

44             if ((d[0][j]>0)&&(d[1][j]>0))tot[min(d[0][j],d[1][j])-1]++;

45     }

46     for(int i=m;i;i--)tot[i-1]+=tot[i];

47     for(int i=0;i<=m;i++)printf("%d ",tot[i]);

48 }

事实上，还可以做到更优秀的复杂度，回到最初的结论

考虑先枚举$x$，并倒序加边，之后维护有多少个点$i$与$x$强连通即可

强连通即分为两部分，即$x$能到达$i$与$i$能到达$x$，且对于每一个具有单调性，即至多修改一次，因此只需要每一次能够快速找到修改的点即可（以下先考虑前者）

假设加入边$(a,b)$，若$a<x$或$b<x$显然无意义，否则分类讨论：

1.若$x$不能到达$a$或$x$能到达$b$，即目前不影响答案，但其会在以后影响答案，即加入边集

2.若$x$能到达$a$但不能到达$b$，从$b$开始dfs搜索，且在经过一条边后删除其

（关于这一做法的正确性：当一条边被经过后，若其内部没有加边显然没有再搜索的意义，而加边不妨直接对其子树内部搜索即可）

对于$i$能否到达$x$，对其反图做同样的过程即可

此时，对于每一条边仅被搜索一次，复杂度即为$o(nm)$，可以通过

另外由于常数问题，建议使用bfs，且这份代码也只能在洛谷上通过（常数问题）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 1005

 4 #define M 200005

 5 struct Edge{

 6     int nex,to,len;

 7 }edge[M<<1];

 8 priority_queue<pair<int,int> >q;

 9 int E,n,m,x,y,head[2][N],d[2][N],vis[N],tot[M];

10 void add(int p,int x,int y,int z){

11     edge[E].nex=head[p][x];

12     edge[E].to=y;

13     edge[E].len=z;

14     head[p][x]=E++;

15 }

16 void calc(int p,int st){

17     memset(d[p],-1,sizeof(d[p]));

18     memset(vis,0,sizeof(vis));

19     d[p][st]=m+1;

20     q.push(make_pair(d[p][st],st));

21     while (!q.empty()){

22         int k=q.top().second;

23         q.pop();

24         if (vis[k])continue;

25         vis[k]=1;

26         for(int i=head[p][k];i!=-1;i=edge[i].nex)

27             if ((edge[i].to>=st)&&(d[p][edge[i].to]<min(d[p][k],edge[i].len))){

28                 d[p][edge[i].to]=min(d[p][k],edge[i].len);

29                 q.push(make_pair(d[p][edge[i].to],edge[i].to));

30             }

31     }

32 }

33 int main(){

34     scanf("%d%d",&n,&m);

35     memset(head,-1,sizeof(head));

36     for(int i=1;i<=m;i++){

37         scanf("%d%d",&x,&y);

38         add(0,x,y,i);

39         add(1,y,x,i);

40     }

41     for(int i=1;i<=n;i++){

42         calc(0,i),calc(1,i);

43         for(int j=i;j<=n;j++)

44             if ((d[0][j]>0)&&(d[1][j]>0))tot[min(d[0][j],d[1][j])-1]++;

45     }

46     for(int i=m;i;i--)tot[i-1]+=tot[i];

47     for(int i=0;i<=m;i++)printf("%d ",tot[i]);

48 }

巴特西

[loj3501]图函数

最新文章

热门文章