首页 > 代码库 > bzoj 1064

bzoj 1064

2024-07-30 16:17:38   223人阅读

题意：戳这里

思路：很明显是一个图论模型。。

        就两种图形：

            1、图中存在环，那么就是所有环的gcd为最大答案。gcd的大于3的最小约数为最小答案

            2、不存在环，那么是每个弱连通块的最长链之和为最大答案，最小答案为3。。

       但是这一题最关键的是实现，实现技巧太赞了。。

       首先，我们可以把每条有向边(u, v)拆成(u, v, 1), (v,  u, -1)

       那么对于第二情况，对于每一个联通块直接随便找一个bfs，然后最长链就是maxdist-mindist+1

       对于第一种情况，可能出现环套环的情况，这样处理起来很麻烦。。

       但实际上很容易发现对于大环套小环实际上大环可以转换成大环-小环剩下的小圈求gcd。。注意这里的小圈不一定是环，因为边有正有负。。

       这样正好处理可以一遍dfs处理。。

      说得很抽象。。直接看这位神犇博客的图吧。。

 

code:

 1 #include <bits/stdc++.h> 2 #define M0(a) memset(a, 0, sizeof(a)) 3 #define x first 4 #define y second 5 #define vii vector< pair<int, int> >::iterator  6 using namespace std; 7 const int maxn = 100010; 8 vector< pair<int, int> > e[maxn]; 9 int n, m;10 11 12 int vis[maxn], d[maxn];13 void init(){14      for (int i = 0; i <= n; ++i) e[i].clear();15      int u, v;16      pair<int, int> tmp;17      for (int i = 0; i < m; ++i){18           scanf("%d%d", &u, &v);19           tmp.x = v, tmp.y = 1;20           e[u].push_back(tmp);21           tmp.x = u, tmp.y = -1;22           e[v].push_back(tmp);23      }24 }25 26 int ans;27 void gao1(){28      int ans1 = ans, ans2 = ans;29      if (ans1 < 3){30           puts("-1 -1"); return;31      }32      for (int j = 3; j <= ans; ++j) if (ans % j == 0){33          ans2 = j; break;34      }35      printf("%d %d\n", ans1, ans2);36 }37 38 39 int bfs(const int s){40     queue<int> q;41     q.push(s), d[s] = 0, vis[s] = 1;42     int u, v, w;43     int maxdist= 0, mindist = 0;44     while (!q.empty()){45         u = q.front();46         q.pop();47         for (vii it = e[u].begin(); it != e[u].end(); ++it){48               v = it->x, w = it->y;49               if (vis[v]) continue;50               d[v] = d[u] + w;51               if (d[v] > maxdist) maxdist = d[v];52               if (d[v] < mindist) mindist = d[v];53               vis[v] = 1, q.push(v);54         }55     }56     return maxdist - mindist + 1;57 }58 59 void gao2(){60      M0(vis), M0(d);61      int ans1 = 0;62      for (int i = 1; i <= n; ++i) if (!vis[i])63          ans1 += bfs(i);64      if (ans1 < 3) puts("-1 -1");65      else printf("%d %d\n", ans1, 3);66 }67 68 void dfs(int u){69       vis[u] = 1;70       int v;71       for (vii it = e[u].begin(); it != e[u].end(); ++it){72             v = it->x;73             if (vis[v])74                  ans = __gcd(ans, abs(d[u] + it->y - d[v]));     75             else76                  d[v] = d[u] + it->y, dfs(v);77       }78 }79 80 void solve(){81      M0(vis), M0(d);82      ans = 0;83      for (int i = 1; i <= n; ++i) if (!vis[i])84            dfs(i);85      if (ans) gao1();86      else gao2();87 }88 89 int main(){90     freopen("a.in", "r", stdin);91     while (scanf("%d%d", &n, &m) != EOF){92          init();93          solve();94     }       95 }
View Code

 

 

       

bzoj 1064


联系
我们