2 条题解

  • 0
    @ 2025-10-8 16:55:15
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=210,inf=0x3f3f3f3f;
    int w[N],a[N][N],d[N][N],mp[N][N],fa[N],id[N];
    int findfa(int x){ return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);} 
    int main()
    {
        int m;scanf("%d",&m);
        memset(mp,0,sizeof(mp));
        for(int x,y,L1,L2,i=1;i<=m;i++)
    	{
            scanf("%d",&x);
            scanf("%d%d%d",&w[x],&L1,&L2);
            for(int j=1;j<=L1;j++) scanf("%d",&y),mp[x][y]=2*x-1;
            for(int j=1;j<=L2;j++) scanf("%d",&y),mp[x][y]=2*x;
        }
        for(int i=1;i<=2*m;i++) fa[i]=i;
        for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(mp[i][j])
    	{
    		int x=mp[i][j],y=mp[j][i];
    		x=findfa(x);y=findfa(y);
    		if(x!=y)fa[x]=y;
    	} 
    	int n=0;memset(id,0,sizeof(id));
    	for(int i=1;i<=2*m;i++) 
    	{
    		int x=findfa(i);
    		if(id[x]==0) id[i]=id[x]=++n;
    		else id[i]=id[x];
    	}
        memset(a,0x0f,sizeof(a));
        for(int i=1;i<=m;i++)
    	{
    		int x=id[2*i-1],y=id[2*i];
    		a[x][y]=a[y][x]=w[i];
    	}
        int ans=25500;
        memcpy(d,a,sizeof(a));
        for(int k=1;k<=n;k++)
    	{
    		for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)
            	ans=min(ans,d[i][j]+a[i][k]+a[k][j]);
        
            for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        }
        printf("%lld\n",ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:55:02
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=210,inf=0x3f3f3f3f;
      int w[N],a[N][N],d[N][N],mp[N][N],fa[N],id[N];
      int findfa(int x){ return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);} 
      int main()
      {
          int m;scanf("%d",&m);
          memset(mp,0,sizeof(mp));
          for(int x,y,L1,L2,i=1;i<=m;i++)
      	{
              scanf("%d",&x);
              scanf("%d%d%d",&w[x],&L1,&L2);
              for(int j=1;j<=L1;j++) scanf("%d",&y),mp[x][y]=2*x-1;
              for(int j=1;j<=L2;j++) scanf("%d",&y),mp[x][y]=2*x;
          }
          for(int i=1;i<=2*m;i++) fa[i]=i;
          for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(mp[i][j])
      	{
      		int x=mp[i][j],y=mp[j][i];
      		x=findfa(x);y=findfa(y);
      		if(x!=y)fa[x]=y;
      	} 
      	int n=0;memset(id,0,sizeof(id));
      	for(int i=1;i<=2*m;i++) 
      	{
      		int x=findfa(i);
      		if(id[x]==0) id[i]=id[x]=++n;
      		else id[i]=id[x];
      	}
          memset(a,0x0f,sizeof(a));
          for(int i=1;i<=m;i++)
      	{
      		int x=id[2*i-1],y=id[2*i];
      		a[x][y]=a[y][x]=w[i];
      	}
          int ans=25500;
          memcpy(d,a,sizeof(a));
          for(int k=1;k<=n;k++)
      	{
      		for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)
              	ans=min(ans,d[i][j]+a[i][k]+a[k][j]);
          
              for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
                  d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
          }
          printf("%lld\n",ans);
          return 0;
      }
      • 1

      *【最短路:floyd求最小环】[USACO4.1] 篱笆回路 Fence Loops

      信息

      ID
      1039
      时间
      1000ms
      内存
      128MiB
      难度
      5
      标签
      递交数
      23
      已通过
      14
      上传者