2017 四川省赛 D.Dynamic Graph
http://blog.csdn.net/mengxiang000000/article/details/75208306
题面下载: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;
- }