icontofig | 发布于 2019-10-12 13:42:57 | 阅读量 143 | bitset topsort

## 题解

mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
for(int i = 1;i <= n;++i)
con[i].reset();
for(int i = 1;i <= n;++i){
if(!c[i])
con[i][i] = 1;
vis[i] = 0;
}
for(int i = 1;i <= n;++i){
tmp[i] = d[i];
if(!d[i]){
qk.push(i);
vis[i] = 1;
}
}
while(!qk.empty()){
int now = qk.front();
qk.pop();
for(int i = 0;i < g[now].size();++i){
int v = g[now][i];
if(c[v] == 0 && c[now] == 0)
con[v] |= con[now];
tmp[v] -= 1;
if(!tmp[v]){
vis[v] = 1;
qk.push(v);
}
}
}
int ans = 0;
for(int i = 1;i <= n;++i){
if(!c[i])
ans += con[i].count() - 1;
}
printf("%d\n",ans);
return;
}
int main(){
while(scanf("%d%d%d",&n,&m,&q) != EOF){
for(int i = 1;i <= n;++i){
c[i] = 0;
d[i] = 0;
g[i].clear();
}
for(int i = 1;i <= m;++i){
scanf("%d%d",&a,&b);
d[b]++;
g[a].push_back(b);
}
while(q--){
scanf("%d",&a);
c[a] ^= 1;
topsort();
}
}
return 0;
}```

143 人读过

0 条评论