城市 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<bits/stdc++.h>

using namespace std;

int n;

int a[];

bool flag[];

int xfindy(int x,int y,int depth){//返回走的步数

    if(depth>n) return -;//边界

    if(flag[]) flag[x]=;//标记服务

    if(x==y&&depth!=) return depth;//成功条件

    else return xfindy(a[x],y,depth+);//继续找

}

int count(int start){

    return xfindy(start,start,);

}

int main(){

    freopen("city.in","r",stdin);

    freopen("city.out","w",stdout);

    cin>>n;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

    }

    //特判：完美的环

    if(count(n-)==n) {cout<<n*n; return ;}

    //把两个最大的环合并

//    for(int i=1;i<=n;i++){

        //如果a[i],a[j]在不同的环内，且

//        for(int j=1;j<=n;j++)

//    }

    long long ans=,max1=-0x3f3f3f,max2=max1,city1=-,city2=-;

    for(int i=;i<=n;i++)

    {

        int huani=count(i);

        if(huani>max1) {

            max1=huani;

            city1=i;

        }

    }

    for(int i=;i<=n;i++)

    {

        if(xfindy(i,city1,)!=-) continue;

        int huani=count(i);

        if(huani>max2) {

            max2=huani;

            city2=i;

        }

    }

    memset(flag,,sizeof(flag));

    flag[]=;

    for(int i=;i<=n;i++){

        //如果从i出发，找不到那两个最大环中的城市，ans+=count(i)^2

        if(flag[i]) continue;

        if(xfindy(i,city1,)==-&&xfindy(i,city2,)==-) ans+=pow(count(i),);

        //如果找的到，说明i在两个最大环内,下一个循环再看

    }

    ans+=pow(max1+max2,);

    cout<<ans;

    return ;

}

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

连通性问题？

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

如果没有呢？

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

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

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

检测有没有指向自己的环

再检测环city小的环

巴特西

嵊州D6T2 城市 city