城市 city

【问题描述】

众所周知，why 是czyz 王国的国王。

czyz 王国一共有n 个城市，每个城市都有一条道路连向一个城市（可能连向这个城市自己）。

同时，对于每一个城市，也只有一条道路连向它。

如果一个人可以通过道路可以从城市x 走向城市y，那么我们称(x,y) 这

个数对是满足条件的。（x 可以等于y）

现在why 可以选择2 个城市改变他们连向的道路，且改变完成之后也要满足上述的条件。

why 想知道，经过这个操作后，最多能有多少满足条件的数对。

【输入格式】

第一行包括一个整数n, 表示城市数。

第二行包括n 个整数a[i]，表示i 有一条道路连向a[i]。

【输出格式】

输出一行一个整数，表示最多能得到多少满足条件的数对。

【输入输出样例】

Input1	Input2
3 2 1 3	5 1 5 4 3 2
Output1	Output2
9	17

【样例解释】

对于样例1，不需要改变，每两个城市之间可以相互到达，ans=3*3=9。

对于样例2，change a[2] to 4, a[3] to 5。

【数据范围】

对于20% 的数据满足：n ≤ 10。

对于50% 的数据满足：n ≤ 100。

对于70% 的数据满足：n ≤ 1000。

对于100% 的数据满足：n ≤ 10^6, 1 ≤ a[i] ≤ n。

Solution

这道题真没想到会超时呢

 

#include
     
      using namespace std;int n;int a[1000000];bool flag[1000000];int xfindy(int x,int y,int depth){
   //返回走的步数    if(depth>n) return -1;//边界     if(flag[0]) flag[x]=1;//标记服务     if(x==y&&depth!=0) return depth;//成功条件     else return xfindy(a[x],y,depth+1);//继续找     }int count(int start){    return xfindy(start,start,0);}int main(){    freopen("city.in","r",stdin);    freopen("city.out","w",stdout);    cin>>n;     for(int i=1;i<=n;i++)    {        cin>>a[i];            }    //特判：完美的环     if(count(n-2)==n) {cout<
      
       max1) {            max1=huani;            city1=i;        }    }     for(int i=1;i<=n;i++)    {        if(xfindy(i,city1,0)!=-1) continue;        int huani=count(i);        if(huani>max2) {            max2=huani;            city2=i;        }    }     memset(flag,0,sizeof(flag));    flag[0]=1;     for(int i=1;i<=n;i++){        //如果从i出发，找不到那两个最大环中的城市，ans+=count(i)^2         if(flag[i]) continue;         if(xfindy(i,city1,0)==-1&&xfindy(i,city2,0)==-1) ans+=pow(count(i),2);        //如果找的到，说明i在两个最大环内,下一个循环再看     }    ans+=pow(max1+max2,2);    cout<
      
     

把互相连着的城市分开一条边，而形成一个环

连通性问题？

如果形成了一个完整的环，那么ans=n^2

如果没有呢？

如果两步之内，不能够形成完美的环呢？

两步，可以把两个环合并！

优先把本身环大的city指向另一个有大环的city，而不是指向少数city围成的环

检测有没有指向自己的环

再检测环city小的环