题面下载:https://icpc-camp-cdn.b0.upaiyun.com/permanent/problems/sichuan-2017.pdf
题目大意:
给你N个点,M条有向边,初始所有点的颜色都是白色,现在有Q个查询,每个查询前先将查询点翻转颜色,然后查询一共存在多少对点,使得点对(u,v)能够存在一条路径从u走到v都是白色的点。
思路:
暴力O(qn^2)超时。
然后考虑bitset优化,设定mmp【i】【j】表示是否存在一条路径使得j能够走到i.
然后过程跑一下拓扑排序即可。
时间复杂度O(qn^2/64);
Ac代码:
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
const int N = 1100+7;
const int MOD = 1e9+7;
int n,m,q,ans;
vector<int>G[303];
int vis[303],c[303],deg[303],temp[303];
void TOP(){
bitset<303>mmp[303];
ans = 0;
queue<int>q;
for(int i=1;i<=n;i++){
if(deg[i]==0)
{
q.push(i);
}
temp[i]=deg[i];
mmp[i][i]=1;
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(c[v]==0&&c[u]==0)
{
mmp[v]=mmp[v]|mmp[u];
}
temp[v]--;
if(temp[v]==0)q.push(v);
}
}
for(int i=1;i<=n;i++)
{
if(c[i]==0)
ans+=mmp[i].count()-1;
}
printf("%d\n",ans);
}
int main(){
while(~scanf("%d%d%d",&n,&m,&q)){
memset(c,0,sizeof(c));
memset(deg,0,sizeof(deg));
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
deg[v]++;
}
for(int x;q--;){
scanf("%d",&x);
c[x]=1-c[x];
TOP();
}
}
return 0;
}