心态炸了(Floyd)必须玄关!!!
查看原帖
心态炸了(Floyd)必须玄关!!!
1168588
FASTergood楼主2024/7/20 14:53

现在已经能验证并查集建的图是对的,dist[i][j]√,但是Floyd一跑就错输出INF,我寻思样例那莫小不至于吧,我™样例都过不了,准备学学SPFA再来了,祝你好运,改对必关注,过样例也关注!!

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
//#define int long long
const int inf = 522133279;
const int maxn = 110;
const int N = 2e2 + 5;
const int M = 2e3;
int dist[maxn][maxn], ma[maxn][maxn];
bool q[maxn][maxn];
int n, m;
int p[M], cnt[M];
int dy[M];
int cur;
//int edge[N];
struct node
{
    int u, v, w;
    bool lside[N], rside[N];
}edge[N];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b)
{
    a = find(a), b = find(b);
    if (a != b)
    {
        p[a] = b;
        cnt[b] += cnt[a];
    }
    return;
}
void floyd()
{

    int ans = 0x3f3f3f3f;


    for(int k=1;k<=cur;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++) ans=min(ans,dist[i][j]+ma[i][k]+ma[k][j]);
        for(int i=1;i<=cur;i++)
            for(int j=1;j<=cur;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    } 
  //  cout <<"&&&&" << cur << endl;
    printf("%d\n", ans);
}

signed main()
{
  //  memset(dist, 0x3f, sizeof(dist));
  //  memset(ma, 0x3f, sizeof(ma));

    scanf("%d", &n);

    for (int i = 0; i <N; i++)
    {
        p[i] = i;
        cnt[i] = 1;
    }
    for (int i = 1;i <= n;i++)
    {
        int x, c, ls, rs;
        scanf("%d%d%d%d", &x, &c, &ls, &rs);
        edge[x].u = 2 * x - 1;
        edge[x].v = 2 * x;
        edge[x].w = c;
        for (int j = 1;j <= ls;j++)
        {
            int k;
            cin >> k;
            edge[x].lside[k] = 1;
        }
        for (int j = 1;j <= rs;j++)
        {
            int k;
            cin >> k;
            edge[x].rside[k] = 1;
        }
    }
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                if (i == j)
                {
                    continue;
                }
                if (edge[i].lside[j] && edge[j].lside[i])
                {
                    merge(edge[i].u, edge[j].u);
                }
                if (edge[i].lside[j] && edge[j].rside[i])
                {
                    merge(edge[i].u, edge[j].v);
                }
                if (edge[i].rside[j] && edge[j].lside[i])
                {
                    merge(edge[i].v, edge[j].u);
                }
                if (edge[i].rside[j] && edge[j].rside[i])
                {
                    merge(edge[i].v, edge[j].v);
                }
            }

        
        }
        cur = 0;
        for (int i = 1;i <= 2 * n;i++) {
            if (p[i] == i) {
                dy[p[i]] = ++cur; // 给剩下的集合根节点重新编号 
                //cur++;
            }
        }
  //dist初始化
        for (int i = 1; i <= cur; i++)
            for (int j = 1; j <= cur; j++)
                if (i == j)
                {
                    ma[i][j] = 0;
                    dist[i][j] = 0;
                }
                else ma[i][j]=dist[i][j] = 0x3f3f3f3f;
        cout << cur << endl;
        //cout << cur << endl;
        for (int i = 1;i <= n;i++) {
            edge[i].u = dy[find(edge[i].u)]; // 去重 
            edge[i].v = dy[find(edge[i].v)];
            int t =edge[i].u;int g =edge[i].v;
            dist[t][g] = dist[g][t] = ma[t][g] = ma[g][t] = edge[i].w;
            // cout << t << " " << g <<" "<<dist[t][g]<<dist[g][t]<<ma[t][g]<< endl;
          //一直到这里Debug都没问题。
 //不排除Floyd写的有问题!!!
        }
          
    floyd();
//cout << cnt[find(11)] << endl;
    return 0;
}

可以用我Dbug时候遗留的code嘎嘎好使,cnt[]是dbug时候用的,样例共7个点,建图没问题

2024/7/20 14:53
加载中...