头像

天天做饿梦

山东财经大学燕山学院




离线:11分钟前


最近来访(74)
用户头像
mmmq
用户头像
踏碎宴席
用户头像
诺亚方舟.
用户头像
Hanson
用户头像
刘家宁
用户头像
Arthur_5
用户头像
Froggy
用户头像
zzx2006
用户头像
她的店里只卖樱花
用户头像
阿兔
用户头像
大家好我叫卢同学
用户头像
福崽儿
用户头像
菜鸟裹裹
用户头像
newSoul
用户头像
Zxx
用户头像
陈笨蛋
用户头像
Loneker
用户头像
itdef
用户头像
灭却
用户头像
琼文


题目链接: https://www.acwing.com/problem/content/1167/

分析:

01分数规划:

把每个串看成一条边,每个串的前两个字母和倒数两个字母看成节点,一个节点两个位置每个有26种情况,每个节点有 $26*26 = 676$ 种情况。

串的长度最大是 $1000$ ,当串最少为 $1$ 个时,要求答案范围为 $(0,1000]$ 。

分析方式同 AcWing 361. 观光奶牛

优化:

若判负环过程中,可能会很长时间,根据设立一个经验值,当更新结点的数量超过了一个比较大的数字后,就可以判断该图中存在负环。

判断无解:

我们目标是寻找一个 mid 使得满足该式的条件下,让mid尽可能大,若答案为 $0$, 即mid为 $0$ 时,该式 $\sum (w - mid * w)$ 还不能大于$0$ 的话,mid变大,该式值会变小,就没有答案满足大于 $0$ 的条件,输出无解。

代码:

#include <iostream>
#include <cstring>

using namespace std;
const int N = 700,M = 100010;
int h[N],e[M],ne[M],w[M],idx;

double dist[N];
bool st[N];
int cnt[N];
int q[N];
int n;

void add(int a,int b,int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool check(double mid)
{
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    int hh = 0,tt = 0;
    for(int i = 0;i < 676;i++)
    {
        q[tt ++] = i;
        st[i] = true;
    }
    int count = 0;
    while(hh != tt)
    {
        int t = q[hh ++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t];~i;i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i] - mid)
            {
                dist[j] = dist[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;
                if(++ count > 10000) return true;//超出一个经验值后,提前退出
                if(cnt[j] >= N) return true;
                if(!st[j])
                {
                    q[tt ++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}
int main()
{
    char str[1010];
    while(scanf("%d",&n),n)
    {
        memset(h,-1,sizeof h);
        idx = 0;
        for(int i = 0;i < n;i++)
        {
            scanf("%s", str);
            int len = strlen(str);
            if(len >= 2)
            {
                int left = (str[0] - 'a') * 26 + str[1] - 'a';//转换成26进制存结点编号
                int right = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                add(left,right,len);
            }
        }

        if(!check(0)) cout<<"No solution"<<endl;
        else
        {
            double l = 0,r = 1000;
            while(r - l > 1e-4)
            {
                double mid = (l + r) / 2;
                if(check(mid)) l = mid;
                else r = mid;
            }

            printf("%lf\n",l);
        }
    }
    return 0;
}



题目链接: https://www.acwing.com/problem/content/363/

二分寻找性质:

记二分答案为 mid,若
$$
\frac {\sum_{i = 1}^{n}f} {\sum_{i = 1}^{m}t} > mid
$$
则答案在右半区间,否则在左半区间。

对等式进行转换:
$$
\sum_{i = 1}^{n}f - mid * \sum_{i = 1}^{m}t > 0
$$
变形得:
$$
\sum_{i = 1}^{n}(f - mid\ *\ t) > 0
$$
我们可以把点权加到以这个点为终点得边权中,该式相当于改图是否存在正环。


求负环常用方法:

① 统计每个点入队次数,如果某个点入队 $n$ 次,则说明存在负环

② 统计当前每个点得最短路中所包含得边数,如果某点的最短路所包含的边数大于等于 $n$,则也说明存在环。

代码:

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1010,M = 5010;

int h[N],e[M],ne[M],wt[M],idx;//wt[]为边权
double dist[N];
int wf[N],cnt[N];
bool st[N];
int q[N];
int n,m;
void add(int a, int b,int c)
{
    wt[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool check(double mid)
{
    memset(dist, 0, sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);

    int hh = 0,tt = 0;
    for(int i = 1;i <= n;i++) 
    {
        q[tt++] = i;
        st[i] = true;
    }

    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t];~i;i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + wf[t] - mid * wt[i])//求正环改变不等号方向
            {
                dist[j] = dist[t] + wf[t] - mid * wt[i];
                cnt[j] = cnt[t] + 1;//更新边个数
                if(cnt[j] >= n) return true;

                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i++) cin>>wf[i];//点权

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    double l = 0,r = 1e6;
    while(r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n",l);
    return 0;
}



题目链接: https://www.acwing.com/problem/content/1148/

建立一个虚拟源点,连向所有发电站,边权为所有发电站的费用,这样问题就转化成了求最小生成树的完整模型。

代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 310,M = 100010;
int n;
int p[N];

struct Edge{
    int a,b,w;
    bool operator <(const Edge &t) const
    {
        return w < t.w;
    }
}e[M];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin>>n;

    for(int i = 1;i <= n;i++) p[i] = i;

    int cnt = 0;
    for(int i = 1;i <= n;i++) 
    {
        int cost;
        cin>>cost;
        e[cnt++] = {0,i,cost}; //虚拟源点
    }

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            int cost;
            cin>>cost;
            if(i < j)
            {
                e[cnt++] = {i,j,cost};
            }
        }
    }

    sort(e,e + cnt);

    int res = 0;
    for(int i = 0;i < cnt;i++)
    {
        int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
        if(a != b) 
        {
            p[a] = b;
            res += w;
        }
    }

    cout<<res<<endl;
    return 0;
}



题目链接: https://www.acwing.com/problem/content/1147/

分析:

首先要连通村庄网络,无线电连通网络 有距离限制,而卫星设备 无距离限制

一种简单的思路:

求一遍最小生成树,为了使 $d$ 值最小,将生成树中从最大的边删除 $k$ 条边,第 $k + 1$ 条边就是最小的 $d$ 值。

代码:

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef pair<int,int> PII;
const int N = 510,M = N * N / 2;
int p[N];
double t[N];//用来存储最小生成树中从小到大的边权
PII q[N];
int n,k;
struct Edge{
    int a,b;
    double w;
    bool operator <(const Edge &t) const
    {
        return w < t.w;
    }
}e[M];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

double get_dist(PII a,PII b)//边权为两点之间的距离
{
    int dx = a.first - b.first;
    int dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}
int main()
{
    cin>>n>>k;

    for(int i = 1;i <= n;i++) p[i] = i;

    for(int i = 0;i < n;i++)
    {
        cin>>q[i].first>>q[i].second;
    }

    int cnt = 0;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < i;j++)
        {
            e[cnt++] = {i,j,get_dist(q[i],q[j])};
        }
    }

    sort(e,e + cnt);
    double res = 0;
    int m = 0;
    for(int i = 0;i < cnt;i++)
    {
        int a = find(e[i].a),b = find(e[i].b);
        double w = e[i].w;
        if(a != b)
        {
            t[m++] = w;//将边权加入最小生成树中
            p[a] = b;
        }
    }

    printf("%.2lf\n",t[m - k]);//m条边减去k条边后,最大的那条边
    return 0;
}

y总思路:

寻找连通块数量和 $d$ 值之间的关系:

发现,当 $k$ 越大的时候,连通块数量越多,连通块内部的 $d$ 值越小。

回到克鲁斯卡尔算法,每次对两个连通块加边,连通块数量少了一个,相当于,$k$ 值加 $1$,使得 $k$ 刚好到规定值,寻找一个特定的 $d$。

看代码吧!!

代码:

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef pair<int,int> PII;
const int N = 510,M = N * N / 2;
int p[N];
PII q[N];
int n,k;
struct Edge{
    int a,b;
    double w;
    bool operator <(const Edge &t) const
    {
        return w < t.w;
    }
}e[M];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

double get_dist(PII a,PII b)
{
    int dx = a.first - b.first;
    int dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}
int main()
{
    cin>>n>>k;

    for(int i = 1;i <= n;i++) p[i] = i;

    for(int i = 0;i < n;i++)
    {
        cin>>q[i].first>>q[i].second;
    }

    int cnt = 0;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < i;j++)
        {
            e[cnt++] = {i,j,get_dist(q[i],q[j])};
        }
    }

    sort(e,e + cnt);
    double res = 0;
    int ans = n;//连通块数量
    for(int i = 0;i < cnt;i++)
    {
        if(ans <= k) break;
        int a = find(e[i].a),b = find(e[i].b);
        double w = e[i].w;
        if(a != b)
        {
            p[a] = b;
            ans--;
            res = w;
        }
    }

    printf("%.2lf\n",res);
    return 0;
}



题目链接: https://www.acwing.com/problem/content/348/

分析:

根据克鲁斯卡尔算法,在两个连通块中选边,对当前生成树扩充为完全图,得使两个连通块中的所有边互相连接

增加边权值的规则:

设 $e$ 为扩充完全图用的边,$w$ 为作为最小生成树添加的边

若 $e < w$ :则说明有比最小生成树 还适合作为最小生成树的边 ,不合法。

若 $e = w$:即可以构造一棵新的最小生成树,不满足 唯一 的要求。

若 $e > w$ :合法,取 $e + 1$ 为用 最小边权之和扩充完全图的最优值

边的数量:

连通块数量 $a$ ,连通块数量 $b$ (为什么减一:两个连通块之间,做 $kruskal$ 算法的时候,已经用了一条边作为最小生成树的边
$$
a * b - 1
$$

代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 6010,M = N * N / 2;

int p[N],sz[N];
int n;

struct Edge{
    int a,b,w;
    bool operator <(const Edge &t)const
    {
        return w < t.w;
    }
}e[M];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i = 1;i <= n;i++) p[i] = i,sz[i] = 1;

        for(int i = 0;i < n - 1;i ++)
        {
            int a,b,w;
            cin>>a>>b>>w;
            e[i] = {a,b,w};
        }

        sort(e,e + n - 1);

        int res = 0;
        for(int i = 0;i < n - 1;i ++)
        {
            int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
            if(a != b)
            {
                res += (sz[a] * sz[b] - 1) * (w + 1);
                sz[b] += sz[a];//将a所在的连通块节点数量加到b所在的连通块中
                p[a] = b;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}



题目链接: https://www.acwing.com/problem/content/1150/

次小生成树 :给一个带权的图,把图的所有生成树按权值从小到大排序,第二小的称为次小生成树。

求解方法:

① 先求最小生成树,再枚举删去最小生成树中的边求解。

② 先求最小生成树,然后依次枚举非树边,然后将该边加入树中,同时从树中去掉一条边,使得最终的图仍是一棵树。则一定可以求出次小生成树。

对于去掉的边的预处理说明:

添加非树边后,从非树边所在的环里,寻找边权尽可能大的边将其删除,存在两种情况:

枚举所有树边,寻找最大边权,若:

最大边权 = 正在添加的边权 $w$ : 删除该最大边权没有区别,因此我们记录 次小边权去删除

最大边权 $\ne$ 正在添加的边权 $w$ : 我们删除最大边权

代码:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 510,M = 10010;

int h[N],w[M * 2],e[M * 2],ne[M * 2],idx;
int p[N],dist1[N][N],dist2[N][N];//dist[a][b]:a 与 b 两点之间的满足条件的尽可能大的边权
int n,m;

struct Edge {
    int a,b,w;
    bool f;//记录是否是树边
    bool operator <(const Edge &t) const
    {
        return w < t.w;
    }
}edge[M];

void add(int a,int b,int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void dfs(int u,int fa,int maxd1,int maxd2,int d1[],int d2[])//当前节点,父节点,最大值,次大值,记录最大值数组,记录次大值数组
{
    d1[u] = maxd1,d2[u] = maxd2;//记录当前点所对应边的最大值,次大值
    for(int i = h[u];~i;i = ne[i])//枚举当前点可扩充的所有点
    {
        int j = e[i];
        if(j != fa)//如果该点扩充的不是父节点
        {
            int t1 = maxd1,t2 = maxd2;//为了不改变当前点的最大值次大值,因为当前点扩充的其他点还要用到该值
            if(w[i] > t1) //比最大值还大,更新最大值,次大值
            {
                t2 = t1,t1 = w[i];
            }
            else if(w[i] > t2 && w[i] < t1)//若小于最大值,大于次大值,只更新次大值
            {
                t2 = w[i];
            }
            dfs(j,u,t1,t2,d1,d2);
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i++) p[i] = i;
    for(int i = 0;i < m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i] = {a,b,c};
    }

    sort(edge,edge + m);

    LL sum = 0;
    for(int i = 0;i < m;i++)
    {
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        int pa = find(a),pb = find(b);
        if(pa != pb)
        {
            p[pa] = pb;
            sum += w;//树边边权之和
            add(a,b,w),add(b,a,w);//最小生成树建图
            edge[i].f = true;//记录是树边
        }
    }

    //对最小生成树中
    for(int i = 1;i <= n;i++) dfs(i,-1,-1e9,-1e9,dist1[i],dist2[i]);//更新以所有点为起点的点i到其他点之间的尽可能大的边权

    LL res = 1e18;
    for(int i = 0;i < m;i++)
    {
        if(!edge[i].f)
        {
            int a = edge[i].a,b = edge[i].b,w = edge[i].w;
            LL t;
            if(w > dist1[a][b])//非树边边权大于要删除边权最大值
            {
                t = sum + w - dist1[a][b];
            }
            else if(w > dist2[a][b])//非树边边权大于要删除边权次大值
            {
                t = sum + w - dist2[a][b];
            }
            res = min(res,t);//所有情况的最小值,即次小生成树边权之和
        }
    }

    cout<<res<<endl;
    return 0;
}



题目连接: https://www.acwing.com/problem/content/1146/

此题拆点:与 AcWing 1131. 拯救大兵瑞恩 一模一样

我的题解: 天天做饿梦-拯救大兵瑞恩

关于不用重新排序优化效率的说明:

代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010,M = N * N,K = 2 * M;

int p[M],ids[N][N];

struct Edge{
    int a,b,w;
}e[K];


int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int n,m,k;

void get_edges()
{
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1},dw[] = {1,2,1,2};//上、右、下、左,总边为1,横边为2

    for(int z = 0;z < 2;z++)
    {
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                for(int u = 0;u < 4;u++)
                {
                    if(u % 2 == z)
                    {
                        int x = i + dx[u],y = j + dy[u],w = dw[u];
                        if(x && x <= n && y && y <= m)
                        {
                            int a = ids[i][j],b = ids[x][y];
                            if(a < b) e[k ++] = {a,b,w};//排除此种等价情况e[k++] = {b,a,w}
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n * m;i++) p[i] = i;

    for(int i = 1,t = 0;i <= n;i++)
    {
        for(int j = 1;j <= m;j++,t ++)
        {
            ids[i][j] = t;
        }
    }

    int x1,y1,x2,y2;
    while(cin>>x1>>y1>>x2>>y2)
    {
        int a = ids[x1][y1],b = ids[x2][y2];
        p[find(a)] = find(b);
    }

    get_edges();//获取边集的权值

    int res = 0;
    for(int i = 0;i < k;i++)
    {
        int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
        if(a != b)
        {
            p[a] = b;
            res += w;
        }
    }
    cout<<res<<endl;
    return 0;
}



题目链接: https://www.acwing.com/problem/content/346/

根据 $\text {floyd}$ 在第一重循环开始的时候:

此时的 d[i][j]:表示从 $i$ 到 $j$,只经过 $1-(k-1)$ 这些点的最短路径。

如图:

代码:

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110,INF = 0x3f3f3f3f;
int g[N][N],dist[N][N];
int pos[N][N],path[N],cnt;
int n,m;

void get_path(int i,int j)//求蓝色线的之间的结点
{
    if(pos[i][j] == 0) return;//若i和j之间没有结点直接返回

    int k = pos[i][j];
    get_path(i,k);//递归求i和k之间的路径
    path[cnt++] = k;//记录k
    get_path(k,j);//递归求k和j之间的路径
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);
    for(int i = 1;i <= n;i++) g[i][i] = 0;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }


    int res = INF;
    memcpy(dist,g,sizeof dist);
    for(int k = 1;k <= n;k++)
    {
        for(int i = 1;i < k;i++)//1到k - 1
        {
            for(int j = i + 1;j < k;j++)
            {
                if((long long)dist[i][j] + g[i][k] + g[k][j] < res)//求环的最小长度
                {
                    res = dist[i][j] + g[i][k] + g[k][j];
                    cnt = 0;
                    path[cnt++] = k;//记录路径k->i->j
                    path[cnt++] = i;
                    get_path(i,j);//获取i和j之间的路径
                    path[cnt++] = j;
                }
            }
        }

        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                if(dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pos[i][j] = k;//k可以更新i和j之间的路径
                }
            }
        }
    }

    if(res == INF) cout<<"No solution."<<endl;//环未被更新,不存在最小环
    else
    {
        for(int i = 0;i < cnt;i++) cout<<path[i]<<" ";
    }

    return 0;
}



题目链接: https://www.acwing.com/problem/content/345/


传递闭包:

若 $A \rightarrow B,B \rightarrow C$ ,则 $A \rightarrow C$


关系:

① 矛盾:存在 $A \rightarrow A$ 即 dist[i][i]

② 若不存在 $A \rightarrow B$ 和 $B \rightarrow A$ 即无定解

③ 否则能确定全部关系

dist[i][j]:表示可以从 i 走到 j,记为 $1$,若不能从 ij 记为 $0$。

代码:

#include <iostream>
#include <cstring>

using namespace std;

const int N = 26;

int dist[N][N],g[N][N];
bool st[N];
int n,m;

void floyd()
{
    memcpy(dist, g, sizeof dist);

    for (int k = 0; k < n; k ++ )
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                dist[i][j] |= dist[i][k] && dist[k][j];\
                //i->k,k->j => i->j 
                //i->j      => i->j
}

int check()//判断关系
{
    for(int i = 0;i < n;i++) //矛盾:A < A
    {
        if(dist[i][i]) return 2;
    }

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < i;j++)
        {
            if(!dist[i][j] && !dist[j][i]) return 0;//无定解:没有 (A < B) 和 (B < A)
        }
    }

    return 1;//有解
}

char get_min()
{
    for (int i = 0; i < n; i ++ )//从所有变量里找最小的那个
        if (!st[i])//记录变量是否已经输出
        {
            bool flag = true;//判断当前这个变量是否是最小的变量
            for (int j = 0; j < n; j ++ )
                if (!st[j] && dist[j][i])//未输出的变量中,如果还存在比当前的变量小的变量,说明当前变量不是最小的变量
                {
                    flag = false;
                    break;
                }
            if (flag)
            {
                st[i] = true;
                return 'A' + i;
            }
        }
}



int main()
{
    while(cin>>n>>m,n || m)
    {
        memset(g,0,sizeof g);
        int type = 0,t;
        for(int i = 1;i <= m;i++)
        {
            char str[5];
            cin>>str;
            int a = str[0] - 'A',b = str[2] - 'A';

            if(!type)
            {
                g[a][b] = 1;
                floyd();

                type = check();
                if(type) t = i;
            }
        }

        if(!type) 
        {
            printf("Sorted sequence cannot be determined.\n");
        }
        else if(type == 2)
        {
            printf("Inconsistency found after %d relations.\n",t);
        }
        else
        {
            memset(st,0,sizeof st);
            printf("Sorted sequence determined after %d relations: ",t);
            for(int i = 0;i < n;i++) printf("%c",get_min());//输出n个变量
            printf(".\n");
        }
    }
    return 0;
}



题目链接: https://www.acwing.com/problem/content/1127/

操作:

① 用 $\text {floyd}$ 算法求出任意两点之间的最短距离

② 求maxd[i],表示和 i 连通的且距离 i 最远的点的距离

情况一:所有maxd[i]的最大值

情况二:枚举在哪两个点之间连边。

i,j 需要满足 d[i,j] = INF.

maxd[i] + maxd[j] + dist[i,j]

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;
typedef pair<int,int> PII;
const int N = 155;
const double INF = 1e20;
double dist[N][N];
double maxd[N];
char g[N][N];
PII q[N];

int n;

double get_dist(PII a,PII b)
{
    double dx = a.first - b.first,dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}
int main()
{
    cin>>n;
    for(int i = 0;i < n;i++) cin>>q[i].first>>q[i].second;

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            cin>>g[i][j];   
        }
    }

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(i != j)
            {
                if(g[i][j] == '1') dist[i][j] = get_dist(q[i],q[j]);//计算两点距离
                else dist[i][j] = INF;//否则初始为正无穷,不可达
            }
        }
    }

    for(int k = 0;k < n;k++)//floyd算法
    {
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < n;j++)
            {
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
            }
        }
    }

    double res1 = 0;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(dist[i][j] < INF)//在一个连通块内
            {
                maxd[i] = max(maxd[i],dist[i][j]);//求两点最大距离
            }
        }
        res1 = max(res1,maxd[i]);//求所有联通块内最大距离的最大距离
    }

    double res2 = INF;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(dist[i][j] >= INF)//不在连通块内
            {
                res2 = min(res2,get_dist(q[i],q[j]) + maxd[i] + maxd[j]);//求最长直径最短
            }
        }
    }

    printf("%lf\n",max(res1,res2));//两种情况求最大值
    return 0;
}