分析

題意說輸入數據有兩個規則：
1 每個i只有一個pi表示i站的目的地 i可以等于pi
2 每個pi都指向唯一的一個站i
那么也就是說i指向的目的只有一個且唯一 每個目的由唯一的始發站出來 所以也就是說 圖中的每一個點只有一條單向邊 那么當我們求最大的數量的可達對時 也就是盡可能構造大圈 所以每一個點 要么形成自回路 要么在一個多點圈中 而連接任意兩個圈的花費就是修改兩站的目的地 所以 把兩個圈構造成一個大圈的花費就是2
所以這道題可以任選兩個最大的圈 連成一個 那么最多的點對 就是這個圈中的點數的平方

題意歸納出來就是盡可能構造大的圈，注意數據有可能會超int

code

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100010; struct node{int id,val;node(int a,int b):id(a),val(b){} }; bool cmp(node a,node b){return a.val>b.val; } vector<node>ans; int k,nex[maxn]; bool bok[maxn]; void dfs(int s){if(!bok[s]){bok[s]=1;k++;dfs(nex[s]);} } int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&nex[i]);}for(int i=1;i<=n;i++){if(!bok[i]){k=0;dfs(i);ans.push_back(node(i,k));}}sort(ans.begin(),ans.end(),cmp);ll sum=0,add=0;bool f=0;if(ans.size()>=2){for(int i=0;i<ans.size();i++){if(i<2){add+=ans[i].val; }else {sum+=1LL*ans[i].val*ans[i].val;//防止溢出}} sum+=1LL*add*add;//防止溢出}else{sum = 1LL*n*n;}printf("%lld\n",sum);return 0; }

WA在爆int…

總結

以上是生活随笔為你收集整理的codeforce 884C - Bertown Subway DFS+图论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。