当前位置：首页 > news >正文

间谍网络（tarjan缩点）

news 来源：原创 2024/5/20 4:12:35

洛谷传送门

看着这道题给人感觉就是tarjan求SCC，然而还得判断是否能控制全部间谍，这就得先从可以贿赂的点dfs一遍。

如果没有全部被标记了，就输出NO，再从没被标记的点里找最小的标号。

如果全被标记，就输出YES，再从入度为0的缩点里找最小的价格，加到ans中，最后输出ans。

——代码

  1 #include <cstdio>
  2 #include <stack>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 
  7 int n, p, r1, cnt, idx, ans = 30000001, minn;
  8 int a[3001], next[8001], to[8001], head[3001], low[3001], dfn[3001], belong[3001], r[3001];
  9 bool ins[3001], vis[3001], mey[3001];
 10 stack <int> s;
 11 
 12 inline void add(int x, int y)
 13 {
 14     to[cnt] = y;
 15     next[cnt] = head[x];
 16     head[x] = cnt++;
 17 }
 18 
 19 void dfs(int u)
 20 {
 21     int i, v;
 22     vis[u] = 1;
 23     mey[u] = 1;
 24     for(i = head[u]; i != -1; i = next[i])
 25     {
 26         v = to[i];
 27         if(!vis[v]) dfs(v);
 28     }
 29 }
 30 
 31 void tarjan(int u)
 32 {
 33     low[u] = dfn[u] = ++idx;
 34     s.push(u);
 35     ins[u] = 1;
 36     int i, v;
 37     for(i = head[u]; i != -1; i = next[i])
 38     {
 39         v = to[i];
 40         if(!dfn[v])
 41         {
 42             tarjan(v);
 43             low[u] = min(low[u], low[v]);
 44         }
 45         else if(ins[v]) low[u] = min(low[u], dfn[v]);
 46     }
 47     if(low[u] == dfn[u])
 48     {
 49         cnt++;
 50         do
 51         {
 52             v = s.top();
 53             s.pop();
 54             ins[v] = 0;
 55             belong[v] = cnt;
 56         }while(u != v);
 57     }
 58 }
 59 
 60 int main()
 61 {
 62     int i, j, k, x, y, u, v;
 63     scanf("%d %d", &n, &p);
 64     for(i = 1; i <= p; i++)
 65     {
 66         scanf("%d", &x);
 67         scanf("%d", &a[x]);
 68     }
 69     memset(head, -1, sizeof(head));
 70     scanf("%d", &r1);
 71     for(i = 1; i <= r1; i++)
 72     {
 73         scanf("%d %d", &x, &y);
 74         add(x, y);
 75     }
 76     for(i = 1; i <= n; i++)
 77      if(!vis[i] && a[i])
 78       dfs(i);
 79     for(i = 1; i <= n; i++)
 80      if(!mey[i])
 81       ans = min(ans, i);
 82     if(ans != 30000001)
 83     {
 84         printf("NO\n%d", ans);
 85         return 0;
 86     }
 87     cnt = 0;
 88     for(i = 1; i <= n; i++)
 89      if(!dfn[i])
 90       tarjan(i);
 91     for(u = 1; u <= n; u++)
 92      for(i = head[u]; i != -1; i = next[i])
 93      {
 94          v = to[i];
 95          if(belong[u] != belong[v]) r[belong[v]]++;
 96      }
 97     ans = 0;
 98     for(i = 1; i <= cnt; i++)
 99      if(r[i] == 0)
100      {
101          minn = 30000001;
102          for(j = 1; j <= n; j++)
103           if(belong[j] == i && a[j])
104            minn = min(minn, a[j]);
105          ans += minn;
106      }
107     printf("YES\n%d", ans);
108     return 0;
109 }