BZOJ1417: Pku3156 Interconnect

1417: Pku3156 Interconnect

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 271  Solved: 136
[Submit][Status][Discuss]

Description

给出无向图G(V, E). 每次操作任意加一条非自环的边(u, v), 每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000)

Input

第一行两个整数N,M 1<=N<=30 0<=M<=1000 接下来M行,每行两个整数X,Y表示两者之间已修好一条道路. 两点之间可以不止修了一条路,也有可能M条路已使N个点成为一个整体.

Output

输出一个小数,表示新修道路条数的期望值,保留六位小数.

Sample Input

4 2
1 2
3 4

Sample Output

1.500000

HINT

Source

题解:我们考虑已存在边对建边是没有影响的,但是对于使图联通是有影响的,所以我们就可以利用这一点进行状态转移

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<vector>
#define ll long long
#define vec vector<int>
using namespace std;
map <vec ,double> q;
vec ve;
int fa[35],size[35],all;
int n,m;
int read()
{
    int x=0,f=1; char ch;
    while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;
    while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);
    return x*f;
}
int find(int x)
{
    if (fa[x]!=x) fa[x]=find(fa[x]); return fa[x];
}
void init()
{
    n=read(); m=read();
    for (int i=1; i<=n; i++) fa[i]=i,size[i]=1;
    for (int i=1; i<=m; i++)
    {
        int u=read(),v=read();
        int q=find(u),p=find(v);
        if (q!=p) fa[q]=p,size[p]+=size[q];
    }
    for (int i=1; i<=n; i++) if (fa[i]==i) ve.push_back(size[i]);
    sort(ve.begin(),ve.end());
    all=n*(n-1)/2;
}
double solve(vec ve)
{
    if (q.count(ve)) return q[ve];
    if (ve.size()==1) return q[ve]=0;
    int sz=ve.size(); int p=0;
    for (int i=0; i<sz; i++) p+=ve[i]*(ve[i]-1)/2;
    double ans=1.0*all/(all-p);
    for (int i=0; i<sz; i++)
    {
        for (int j=0; j<i; j++)
        {
            vec v=ve;
            v[j]+=v[i]; swap(v[i],v[sz-1]);
            v.pop_back(); sort(v.begin(),v.end());
            ans+=1.0*ve[i]*ve[j]/(all-p)*solve(v);
        }
    }
    return q[ve]=ans;
}
int main()
{
    init();
    printf("%0.6lf\n",solve(ve));
}

时间: 08-20

BZOJ1417: Pku3156 Interconnect的相关文章

【BZOJ1417】Pku3156 Interconnect 记忆化搜索

[BZOJ1417]Pku3156 Interconnect Description 给出无向图G(V, E). 每次操作任意加一条非自环的边(u, v), 每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000) Input 第一行两个整数N,M 1<=N<=30 0<=M<=1000 接下来M行,每行两个整数X,Y表示两者之间已修好一条道路. 两点之间可以不止修了一条路,也有可能M条路已使N个点成为一个整体. Outp

uva 1390 - Interconnect(期望+哈希+记忆化)

题目连接:uva 1390 - Interconnect 题目大意:给出n表示有n个点,m表示有m条边,现在任选两点建立一条边,直到整个图联通,问说还需建立边数的期望,建过边的两点仍可以建边. 解题思路:哈希的方法很是巧妙,将各个联通分量中节点的个数c[i]转换成一个30进制的数(因为节点个数最多为30),因为结果很大,所以对1e5+7取模.获得的哈希值作为插入和搜索的起点. #include <cstdio> #include <cstring> #include <alg

Using an open debug interconnect model to simplify embedded systems design

Using an open debug interconnect model to simplify embedded systems design Tom Cunningham, Freescale Semiconductor AUGUST 29, 2007 Technology people are generally familiar with the Open Systems Interconnection model for computer networks and protocol

PatentTips - Device virtualization and assignment of interconnect devices

BACKGROUND Standard computer interconnects, particularly for personal computers or workstations, may employ a bus such as Peripheral Component Interconnect ("PCI"), Industry Standard Architecture ("ISA"), or Extended ISA ("EISA&qu

PatentTips - Apparatus and method for a generic, extensible and efficient data manager for virtual peripheral component interconnect devices (VPCIDs)

BACKGROUND A single physical platform may be segregated into a plurality of virtual networks. Here, the physical platform incorporates at least one virtual machine monitor (VMM). A conventional VMM typically runs on a computer and presents to other s

UVA 1390 Interconnect

https://vjudge.net/problem/UVA-1390 题意: 给出n个点m条边的无向图, 每次随机加一条非自环的边,(加完后可出现重边), 添加每条边的概率是相等的 求使图连通的期望添边次数 只关心图的连通状况,即连通块的个数和大小 所以可以用{a1,a2,a3……an} 表示状态(n个连通块,每个连通块大小为ai) 添加一条边后有两种可能 1.状态不变 2.状态变为 {a1,……ai+aj,……a_n-1} 将状态哈希 dp[i]表示哈希后为i的状态 添边至连通的期望次数 d

POJ 3156 - Interconnect (概率DP+hash)

题意:给一个图,有些点之间已经连边,现在给每对点之间加边的概率是相同的,问使得整个图连通,加边条数的期望是多少. 此题可以用概率DP+并查集+hash来做. 用dp(i,j,k...)表示当前的每个联通分量的点数分别是i,j,k...(连通分量的个数不固定)时,加边的期望. 这样以dp(i,j,k)为例分析状态转移的过程,dp(i,j,k)=p1*dp(i,j,k)+p2*dp(i+j,k)+p3*dp(i,j+k)+p4*dp(j,i+k)+1. 终止条件是dp(n)=0,因为此时图一定联通,

TCP及socket通信原理

一.网络互联模型 因特网在刚面世时,只有同一制造商生产的计算机才能彼此通信,制定网络互联模型的目的就是为异种的计算机互连提供一个共同的基础和标准框架,并为保持相关标准的一致性和兼容性提供共同的参考. 互联参考模型: OSI七层模型(Open System Interconnect):应用层.表示层.会话层.传输层.网络层.数据链路层.物理层 DoD四层模型:是OSI七层模型的浓缩版,包括 进程/应用层.主机到主机层.因特网层.网络接入层 以上两种模型是层次型的,分层模型的优点主要在于: ①将网络

RAC集群节点故障模拟测试

RAC节点故障模拟测试 重启单个RAC 节点模拟测试模拟操作步骤使用shutdown –Fr的方式重启节点,查看系统反应和数据库重新启动的时间.预期测试结果重启单个节点,vip将会切换到另外一个节点.系统重新启动之后,节点上的集群服务和数据库将会自动启动,重新加入集群.Vip也将切换回原始节点.测试过程记录使用shutdown 命令重启第三节点第三节点关闭之后查看crs服务状态RAC02:oracle:db2 > crs_stat -tName           Type