题意
300个点的无环图，开始都是白色，每次改变某个节点的颜色(黑/白)，问有多少对白点之间存在只有白点的路径。
题解
类似floyd，求出两点之间的路径条数。然后白到黑就删去对应路径，黑到白就增加对应路径。再扫一遍路径数大于0的白点对。
代码
代码语言：javascript复制#include <cstdio>
#include <cstring>
#define N 301
int g[N][N];
int f[N][N];
bool c[N];
int main(){
int n,m,q;
while(~scanf("%d%d%d",&n,&m,&q)){
memset(g,0,sizeof g);
memset(f,0,sizeof f);
memset(c,0,sizeof c);
for(int i=1,a,b;i<=m; i){
scanf("%d%d",&a,&b);
g[a][b]=f[a][b]=1;
}
for(int k=1;k<=n; k)
for(int i=1;i<=n; i)
for(int j=1;j<=n; j)
f[i][j] =f[i][k]*f[k][j];
int ans=0;
for(int i=1;i<=n; i)
for(int j=1;j<=n; j)
ans =(f[i][j]>0);
while(q--){
int v;
scanf("%d",&v);
c[v]=!c[v];
if(c[v]){//white->black
for(int i=1;i<=n; i){
for(int j=1;j<=n; j)
f[i][j]-=f[i][v]*f[v][j];
f[i][v]=f[v][i]=0;
}
}
else{//black->white
for(int i=1;i<=n; i){
for(int j=1;j<=n; j)
if(!c[i]&&!c[j]){
f[v][i] =g[v][j]*f[j][i];
f[i][v] =f[i][j]*g[j][v];
}
if(!c[i]){
f[v][i] =g[v][i];
f[i][v] =g[i][v];
}
}
for(int i=1;i<=n; i)
for(int j=1;j<=n; j)
if(!c[i]&&!c[j])
f[i][j] =f[i][v]*f[v][j];
}
int ans=0;
for(int i=1;i<=n; i)
for(int j=1;j<=n; j)
if(!c[i]&&!c[j]&&f[i][j]) ans;
printf("%dn", ans);
}
}
return 0;
}
