精华内容
下载资源
问答
  • HDU 4081(最小生成树

    2019-09-25 23:11:27
    题意:给出一个,每个顶点有一个权值,要求求出一个生成树,这个树上的某一边长变为0,...先用prim算法计算最小生成树计算的时候已经在树上的点和正在添加的点之间路径上的最大边权就是添加的这条边或者和它连边...

    题意:给出一个图,每个顶点有一个权值,要求求出一个生成树,这个树上的某一边长变为0,求该边两端点权值之和与总边权的最大比值。

    思路:枚举权值为0的边,如过该边在最小生成树上,直接减去边权,如果不在树上,添加边必然产生环,此时最小总边权可以通过减去这个环上的最大边权求得。先用prim算法计算最小生成树,计算的时候已经在树上的点和正在添加的点之间路径上的最大边权就是添加的这条边或者和它连边的那个点对应的最大边权。求出所有最大边权之后枚举加边即可。

    #include<bits/stdc++.h>
    #define pb push_back
    #define se second
    #define fs first
    #define sq(x) (x)*(x)
    #define eps 0.0000000001
    using namespace std;
    typedef long long ll;
    typedef pair<ll,ll> P;
    const int maxv=1005;
    int T;
    int n;
    int po[maxv],X[maxv],Y[maxv];
    double G[maxv][maxv];
    double maxlen[maxv][maxv];
    bool used[maxv];
    bool eused[maxv][maxv];
    double mincost[maxv];
    int mincostfrom[maxv];
    double prim(){
        memset(used,0,sizeof used);
        memset(maxlen,0,sizeof maxlen);
        memset(eused,0,sizeof eused);
        for(int i=0;i<maxv;i++){
            maxlen[i][i]=0;
        }
        double ans=0;
        mincostfrom[0]=0;
        for(int i=0;i<=n;i++) mincost[i]=1e20;
        mincost[0]=0;
        int added=0;
        while(added<n){
            double cost=1e8;
            int from,to;
            for(int i=0;i<n;i++){
                if(!used[i]&&mincost[i]<cost){
                    from=mincostfrom[i];
                    cost=mincost[i];
                    to=i;
                }
            }
            eused[from][to]=eused[to][from]=1;
            added++;
            ans+=cost;
            used[to]=1;
            for(int i=0;i<n;i++){
                if(used[i]&&to!=i)
                maxlen[to][i]=maxlen[i][to]=max(maxlen[i][from],max(maxlen[to][i],cost));
            }
            for(int i=0;i<n;i++){
                if(!used[i]&&G[to][i]<mincost[i]){
                    mincostfrom[i]=to;
                    mincost[i]=G[to][i];
                }
            }
        }
        return ans;
    }
    int main(){
        freopen("/home/files/CppFiles/in","r",stdin);
        cin>>T;
        while(T--){
            cin>>n;
            for(int i=0;i<n;i++){
                scanf("%d%d%d",X+i,Y+i,po+i);
            }
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){
                    double dis=sqrt((double)sq(X[i]-X[j])+sq(Y[i]-Y[j]));
                    G[i][j]=G[j][i]=dis;
                }
            }
            double mst=prim();
            double ans=0;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){
                    double popu=po[i]+po[j];
                    double tollen;
                    if(eused[i][j]){
                        tollen=mst-G[i][j];
                    }
                    else tollen=mst-maxlen[i][j];
                    ans=max(ans,popu/tollen);
                }
            }
            printf("%.2f\n",ans);
        }
        return 0;
    }
    View Code

     

    转载于:https://www.cnblogs.com/Cw-trip/p/4675553.html

    展开全文
  •  机智的小B决定陪着小A玩游戏,他从魔法的世界里变出一张无向联通,每条边上都有边权。小B定义一条路径的权值为所有经过边中的最大权值,小A则定义两点的最短路径为所有路径中权值最小的路径权。 每次小A先选出...

    5163 -- 【11.04题目】玩游戏

    Description

      小A得了忧郁综合症,小B正在想办法开导她。
      机智的小B决定陪着小A玩游戏,他从魔法的世界里变出一张无向联通图,每条边上都有边权。小B定义一条路径的权值为所有经过边中的最大权值,小A则定义两点的最短路径为所有路径中权值最小的路径权。
      每次小A先选出两个点m1,m2,然后小B选出两个点b1,b2,计算出它们的最短路径m,b,然后小B会拿出两堆灵魂宝石,一堆有m个,另一堆有b个。然后小A先从一堆中选出若干个灵魂宝石拿走,接下来小B重复同样的操作,如此反复,直到取走最后一颗灵魂宝石,然后取走最后一颗宝石的人获胜。
      小B认为这样游戏太简单,于是他会不定期向这张图上加上一些边,以增大游戏难度。
      小A具有预知未来的能力,她看到了自己和小B在未来游戏中的选择,以及小B增加的边。现在对于每次游戏,小A想知道自己是否存在必胜的方法。但是预知未来已经消耗了她太多精力,出于疲惫她只好找到了你。

    Input

      第一行两个数N和M,表示这张无向图初始的点数与边数;
      接下来M行,每行三个数u,v,q,表示点u和点v之间存在一条权值为q的边;
      接下来一行一个数Q,表示操作总数;
      接下来Q行,表示操作,每行格式为下面两条中的一条:
      1.add u v q:表示在u与v之间加上一条边权为q的边;
      2.game m1 m2 b1 b2:表示一次游戏,其中小A的选择点m1,m2,小B的选择点b1,b2。
      数据保证1≤u,v,m1,m2,b1,b2≤n,1≤q,m1≠m2 且 b1≠b2

    Output

      对于每个game输出一行,若小A存在必胜策略,则输出“madoka”,否则输出“Baozika”,以回车结尾

    Sample Input

    5 6 1 2 3 2 3 6 4 2 4 5 3 5 3 4 5 5 1 5 4 game 1 3 4 3 game 1 5 2 4 add 2 5 4 game 1 5 3 4

    Sample Output

    Baozika madoka madoka

    Hint




     
     
     
    我们先求出一个最小生成树,然后每加上一条边我们就重新dfs一遍维护
    至于那个博弈实际上就是一个nim博弈,直接异或起来判断是否是0就可以了
    code:
      1 #include<iostream>
      2 #include<cstdio>
      3 #include<cstring>
      4 #include<algorithm>
      5 #include<string>
      6 #define N 500005
      7 using namespace std;
      8 long long n,m;
      9 struct node {
     10     long long u,v,w,used;
     11 } e[N],t[N];
     12 int first[N],nxt[N],cnt;
     13 inline void add(long long u,long long v,long long w,long long d) {
     14     e[++cnt].u=u;
     15     e[cnt].v=v;
     16     e[cnt].w=w;
     17     e[cnt].used=d;
     18     nxt[cnt]=first[u];
     19     first[u]=cnt;
     20 }
     21 inline bool cmp(const node&a,const node&b) {
     22     return a.w<b.w;
     23 }
     24 long long fa[N];
     25 inline long long find(long long x) {
     26     if(x!=fa[x])return fa[x]=find(fa[x]);
     27     return fa[x];
     28 }
     29 inline void merge(long long x,long long y) {
     30     long long f1=find(x),f2=find(y);
     31     if(f1!=f2) {
     32         fa[f1]=f2;
     33     }
     34 }
     35 inline void kruskal() {
     36     long long cnt_=0;
     37     for(long long i=1; i<=m; ++i) {
     38         long long u=t[i].u,v=t[i].v,w=t[i].w;
     39         if(find(u)!=find(v)) {
     40             merge(u,v);
     41             add(u,v,w,1);
     42             add(v,u,w,1);
     43             cnt_++;
     44             if(cnt_==n-1)return;
     45         }
     46     }
     47 }
     48 struct T {
     49     long long id,max;
     50 };
     51 long long dep[N],mx[N][30],f[N][30],bianhao[N][30];
     52 T lca(long long x,long long y) {
     53     if(dep[x]<dep[y])swap(x,y);
     54     long long id,max0=0;
     55     for(long long i=15; i>=0; i--) {
     56         if(dep[f[x][i]]>=dep[y]) {
     57             if(max0<mx[x][i]) {
     58                 max0=mx[x][i];
     59                 id=bianhao[x][i];
     60             }
     61             x=f[x][i];
     62         }
     63         if(x==y)return (T) {
     64             id,max0
     65         };
     66     }
     67     for(long long i=15; i>=0; i--) {
     68         if(f[x][i]==f[y][i])continue;
     69         if(max0<mx[x][i]) {
     70             max0=mx[x][i];
     71             id=bianhao[x][i];
     72         }
     73         if(max0<mx[y][i]) {
     74             max0=mx[y][i];
     75             id=bianhao[y][i];
     76         }
     77         x=f[x][i];
     78         y=f[y][i];
     79     }
     80     T temp;
     81     if(max0<mx[y][0]) {
     82         max0=mx[y][0];
     83         id=bianhao[y][0];
     84     }
     85     if(max0<mx[x][0]) {
     86         max0=mx[x][0];
     87         id=bianhao[x][0];
     88     }
     89     temp.id=id,temp.max=max0;
     90     return temp;
     91 }
     92 long long dis[N];
     93 inline void dfs(long long x) {
     94     for(long long i=first[x]; i; i=nxt[i]) {
     95         if(!e[i].used)continue;
     96         long long v=e[i].v;
     97         if(v==f[x][0])continue;
     98         f[v][0]=x;
     99         bianhao[v][0]=i;
    100         dep[v]=dep[x]+1;
    101         mx[v][0]=e[i].w;
    102         dfs(v);
    103     }
    104 }
    105 inline void build() {
    106     f[1][0]=1;
    107     dep[1]=0;
    108     dfs(1);
    109     for(long long i=1; i<=15; ++i) {
    110         for(long long j=1; j<=n; ++j) {
    111             f[j][i]=f[f[j][i-1]][i-1];
    112             mx[j][i]=max(mx[j][i-1],mx[f[j][i-1]][i-1]);
    113             if(mx[j][i]==mx[j][i-1])bianhao[j][i]=bianhao[j][i-1];
    114             else bianhao[j][i]=bianhao[f[j][i-1]][i-1];
    115         }
    116     }
    117 }
    118 inline long long read(){
    119     long long x=0,f=1;
    120     char c=getchar();
    121     while(!isdigit(c)){
    122         if(c=='-')f=-1;
    123         c=getchar();
    124     }
    125     while(isdigit(c)){
    126         x=(x<<3)+(x<<1)+c-'0';
    127         c=getchar();
    128     }
    129     return x*f;
    130 }
    131 int main() {
    132 //    freopen("game1.in","r",stdin);
    133     n=read(),m=read();
    134     for(long long i=1; i<=n; ++i)fa[i]=i;
    135     for(long long i=1; i<=m; ++i) {
    136         t[i].u=read(),t[i].v=read(),t[i].w=read();
    137     }
    138     sort(t+1,t+m+1,cmp);
    139     kruskal();
    140     build();
    141     //cout<<e[lca(2,5).id].u<<" "<<e[lca(2,5).id].v<<"!!!!!";
    142     long long Q;
    143     Q=read();
    144     while(Q--) {
    145         string k;
    146         cin>>k;
    147         if(k=="add") {
    148             long long u,v,w;
    149             u=read(),v=read(),w=read();
    150             T temp=lca(u,v);
    151             if(temp.max>w) {
    152                 e[temp.id].used=0;
    153 //                cout<<u<<" "<<v<<" u->"<<e[temp.id].u<<" v->"<<e[temp.id].v<<" max->"<<temp.max<<'\n';
    154                 if(e[temp.id+1].u==e[temp.id].v&&e[temp.id+1].v==e[temp.id].u) {
    155                     e[temp.id+1].used=0;
    156                 } else e[temp.id-1].used=0;
    157                 add(u,v,w,1);
    158                 add(v,u,w,1);
    159                 build();
    160             }
    161         } else {
    162             long long a,b,c,d;
    163             a=read(),b=read(),c=read(),d=read();
    164             long long max1=lca(a,b).max,max2=lca(c,d).max;
    165 //            cout<<"max1->"<<max1<<" max2->"<<max2<<" "<<'\n';
    166             if(max1^max2) {
    167                 cout<<"madoka"<<'\n';
    168             } else {
    169                 cout<<"Baozika"<<'\n';
    170             }
    171         }
    172     }
    173     return 0;
    174 }

    over

    转载于:https://www.cnblogs.com/saionjisekai/p/9867132.html

    展开全文
  • 最后相当于求0-n+1的这条路上的最大边权。 列数就是该点的横坐标。 建完套一下Krustra的板子就好了。 #pragma GCC optimize(2) #pragma GCC optimize(3) #include &lt;bits/stdc++.h&gt; using n...

    题目链接

    本来以为是一道计算几何,然后看大佬的代码发现竟然是最小生成树??
    能想到最小生成树很诡异,建图也很诡异。
    最后相当于求0-n+1的这条路上的最大边权。

    列数就是该点的横坐标。

    建完图套一下Krustra的板子就好了。

    #pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include <bits/stdc++.h>
    using namespace std;
    #define clr(s, x) memset(s, x, sizeof(s))
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    inline int read(){int r=0;char c=getchar();while(c<'0'||c>'9') {c=getchar();}while(c>='0'&&c<='9') {r=r*10+c-'0';c=getchar();}return r;}
    inline ll readll(){ll r=0;char c=getchar();while(c<'0'||c>'9') {c=getchar();}while(c>='0'&&c<='9') {r=r*10+c-'0';c=getchar();}return r;}
    inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
    inline ll gcd(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
    const double eps = 1e-8;
    const ll LLINF = 0x3f3f3f3f3f3f3f3f;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9+7;
    const int MAXN = 1e5;
    const int MAXM = 1e5;
    
    struct EDGE{
    	int u, v;
    	double w;
    };
    bool cmp(EDGE a, EDGE b){
    	return a.w < b.w;
    }
    vector<EDGE> G;
    double x[MAXN], y[MAXN];
    int pre[MAXN];
    double dist(int i, int j){
    	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    }
    int find(int x){
    	if(x == pre[x])	return x;
    	else	return pre[x] = find(pre[x]);
    }
    void merge(int x, int y){
    	int fx = find(x);
    	int fy = find(y);
    	if(fx != fy)	pre[fx] = fy;
    }
    int main(int argc, char const *argv[])
    {
    	ios::sync_with_stdio(false);
    	double l;
    	int n;
    	G.clear();
    	cin >> l >> n;
    	for(int i=1; i<=n; ++i)	cin >> x[i] >> y[i];
    	for(int i=1; i<n; ++i){
    		for(int j=i+1; j<=n; ++j){
    			G.push_back((EDGE){i, j, dist(i,j)/2.0});
    		}
    	}
    	for(int i=1; i<=n; ++i){
    		G.push_back((EDGE){i, 0, x[i]});
    		G.push_back((EDGE){i, n+1, l-x[i]});
    	}
    	sort(G.begin(),G.end(),cmp);
    	for(int i=0; i<=n+1; ++i)	pre[i] = i;
    	for(int i=0; ; ++i){
    		merge(G[i].u, G[i].v);
    		if(find(0) == find(n+1)){
    			cout << fixed << setprecision(2) << G[i].w <<endl;
    			break;
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 题目描述 ...如果藏宝图是真,那么经过点x的边权平均数最大的那个x是藏着宝物地方。请计算这是不是真藏宝图,如果是真藏宝之处在哪里。 输入 输入数据第一行一个数T,表示T组数据。对于...

    题目描述

    Czy爬上黑红树,到达了一个奇怪的地方……
    Czy发现了一张奇怪的藏宝图。图上有n个点,m条无向边。已经标出了图中两两之间距离dist。但是czy知道,只有当图刚好又是一颗树的时候,这张藏宝图才是真的。如果藏宝图是真的,那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图,如果是真的藏宝之处在哪里。

     

    输入

    输入数据第一行一个数T,表示T组数据。
    对于每组数据,第一行一个n,表示藏宝图上的点的个数。
    接下来n行,每行n个数,表示两两节点之间的距离。

     

    输出

    输出一行或两行。第一行”Yes”或”No”,表示这是不是真的藏宝图。
    若是真的藏宝图,第二行再输出一个数,表示哪个点是藏宝之处。
     

     

    样例输入

    复制样例数据

    2
    3
    0 7 9
    7 0 2
    9 2 0
    3
    0 2 7
    2 0 9
    7 9 0
    

    样例输出

    Yes
    1
    Yes
    3
    

     

    提示

    第一棵树的形状是1--2--3。1、2之间的边权是7,2、3之间是2。
    第二棵树的形状是2--1--3。2、1之间的边权是2,1、3之间是7。

    对于30%数据,n<=50,1<=树上的边的长度<=10^9。
    对于50%数据,n<=600.
    对于100%数据,1<=n<=2500,除30%小数据外任意0<=dist[i][j]<=10^9,T<=5

      1 #include <iostream>
      2 #include <bits/stdc++.h>
      3 using namespace std;
      4 const int N = 2505;
      5 typedef long long ll;
      6 ll mapp[N][N],nmp[N][N];
      7 ll d[N],from[N];
      8 bool vis[N];
      9 struct Edge
     10 {
     11     int u;
     12     int v;
     13     ll w;
     14     int net;
     15 } edge[N*2];
     16 int cnt_edge=0;
     17 int head[N*2];
     18 void add_edge(int fr,int to,ll w)
     19 {
     20     edge[cnt_edge].v=to;
     21     edge[cnt_edge].w=w;
     22     edge[cnt_edge].net=head[fr];
     23     head[fr]=cnt_edge++;
     24 }
     25 void init()
     26 {
     27     memset(head,-1,sizeof(head));
     28     memset(nmp,0,sizeof(nmp));
     29     memset(d,0x7f7f,sizeof(d));
     30     memset(vis,0,sizeof(vis));
     31     memset(from,0,sizeof(from));
     32     memset(edge,0,sizeof(edge));
     33     cnt_edge=0;
     34 }
     35 int n;
     36 void prim()
     37 {
     38     d[1]=0;
     39     for(register int i=1; i<=n; i++)
     40     {
     41         int x=0;
     42         for(register int j=1; j<=n; j++)
     43         {
     44             if(!vis[j]&&(x==0||d[j]<d[x]))
     45                 x=j;
     46         }
     47         vis[x]=1;
     48         for(register int y=1; y<=n; y++)
     49         {
     50             if(!vis[y]&&mapp[x][y]<d[y])
     51             {
     52                 from[y]=x;
     53                 d[y]=mapp[x][y];
     54             }
     55 
     56         }
     57     }
     58 
     59 }
     60 void dfs(int fa,int fr,int now)
     61 {
     62     for(register int i=head[fr];i!=-1;i=edge[i].net)
     63     {
     64         int temp=edge[i].v;
     65         if(fa==temp)
     66             continue;
     67         nmp[now][temp]=nmp[now][fr]+edge[i].w;
     68         dfs(fr,temp,now);
     69     }
     70 }
     71 
     72 int main()
     73 {
     74     int T;
     75     cin>>T;
     76     while(T--)
     77     {
     78         cin>>n;
     79         bool flag=true;
     80         for(register int i=1; i<=n; i++)
     81         {
     82             for(register int j=1; j<=n; j++)
     83             {
     84                 ll x;
     85                 scanf("%lld",&x);
     86                 mapp[i][j]=x;
     87                 if(i==j&&x!=0)
     88                 {
     89                     flag=false;
     90                 }
     91             }
     92         }
     93         for(register int i=1; i<=n; i++)
     94         {
     95             for(register int j=1; j<=i; j++)
     96             {
     97                 if(mapp[i][j]!=mapp[j][i])
     98                 {
     99                     flag=false;
    100                     break;
    101                 }
    102             }
    103         }
    104         if(flag)
    105         {
    106             init();
    107             prim();
    108             for(register int i=2;i<=n;i++)
    109             {
    110                 add_edge(i,from[i],d[i]);
    111                 add_edge(from[i],i,d[i]);
    112             }
    113             for(register int i=1;i<=n;i++)
    114             {
    115                 dfs(-1,i,i);
    116             }
    117             for(register int i=1;i<=n;i++)
    118             {
    119                 for(register int j=1;j<=n;j++)
    120                 {
    121                     if(mapp[i][j]!=nmp[i][j])
    122                     {
    123                         flag=false;
    124                     }
    125                 }
    126             }
    127         }
    128         if(flag)
    129         {
    130             double maxx=-1;
    131             int num;
    132             double tot=0;
    133             for(register int i=1;i<=n;i++)
    134             {
    135                 double sum=0;
    136                 tot=0;
    137                 for(register int j=head[i];j!=-1;j=edge[j].net)
    138                 {
    139                     sum+=edge[j].w;
    140                     tot++;
    141                 }
    142                 if(tot)
    143                 {
    144                     sum/=(tot*1.0);
    145                 }
    146                 if(sum>maxx)
    147                 {
    148                     maxx=sum;
    149                     num=i;
    150                 }
    151             }
    152             printf("Yes\n");
    153             cout << num << endl;
    154         }
    155         else
    156             cout << "No" << endl;
    157     }
    158 
    159     //cout << "Hello world!" << endl;
    160     return 0;
    161 }
    View Code

     

    转载于:https://www.cnblogs.com/SoulSecret/p/10303652.html

    展开全文
  • 2、根据这两步的结果求出每个点到达根节点所经道路中权值最大的边,如果这个点与根节点有边相连并且边权小于之前求出的最大边,那么更新答案并删边。 3、重复步骤2,直到没有可更新的点或者根节点度数达到限...
  • 题目大意:在一个完全图中找一棵生成树,满足其中一条的两个邻接点的点之和除以该生成树的所有比安全和的比例...首先计算图的最小生成树,设最小生成树的总长度为ans;然后枚举所有的点对(i,j),如果(i,j...
  • 2.类似prim从点p开始扩展出“最大生成树”,记录最后扩展顶点和最后扩展边 3.计算最后扩展到顶点切割值(即与此顶点相连所有边权和),若比min小则更新min 4.合并最后扩展那条边两个端...
  • 显然最小的最大路径在最小生成树上(最小生成树=最小瓶颈生成树) 于是我们建出kruskal重构树,两个节点的d值就是lca代表的边的边权,问题转化为对于每个lca计算以它为lca的且满足$|c_u-c_v|$的点对的个数 对于每...
  • poj 2914 Minimum Cut 无向图最小

    千次阅读 2010-11-13 11:36:00
    Stoer-Wagner算法 附模板 Stoer-Wagner算法: prim算法不仅仅可以求最小生成树,也可以求“最大生成树”。最小割集Stoer-Wagner算法就是典型应用实例。 求解最小割集普遍采用Stoer-...
  • CF 609E, 链剖分

    2016-09-24 09:21:00
    题目大意:给你一个联通无向,问你包含某条边的最小生成树的大小是多少 解:做一个最小生成树,如果询问在树上,则答案是最小生成树,否则则是这条+树构成环上去掉一条最大后得到树。这里用树剖处理...
  • 无向图最小割,stoer_wagner算法题意: 给一副无向,求一组最小割集,将分成两份 题解 某算法刚好可解决 stoer_...3.计算最后扩展到顶点切割值(即与此顶点相连所有边权和),若比min小更新min 4.合
  • 2.从点P用“类似”prims算法扩展出“最大生成树”,记录最后扩展顶点和最后扩展边 3.计算最后扩展到顶点切割值(即与此顶点相连所有边权和),若比min小更新min 4.合并最后扩展那条边两个端点为
  • POJ2914无向图最小割Stoer-Wagner算法

    千次阅读 2012-07-09 22:57:49
    /* ...求解最小割集普遍采用Stoer-Wagner算法: 1.min=MAXINT,固定一个顶点P 2.从点P用类似prims算法扩展出“最大生成树”,记录最后扩展顶点和最后扩展...3.计算最后扩展到顶点切割值(即与此顶点相连所有边权
  • NOIP 2013 P1967 货车运输

    2019-07-03 20:28:00
    题中可以发现货车最后载重量是由权值最小的一条边决定,所以我们求最大生成树 求完最大生成树后我们得到一个森林 现在转化为了求两点路径经过边的边权的最小值,用倍增算法进行计算 #include <bits/...
  • 题意:在无向中找一条1到n路径,使其中max{a}+max{b}max\{a\}+max\{b\}最小。题解:lct+类似最小生成树。...用lct维护一个类似最小生成树的东西,对于一条边,都看作一个点,边权做点权,向他原来连接点连
  • ACM算法模版大集合

    2009-10-15 23:18:39
    最小生成树 第k小生成树 最优比率生成树 0/1分数规划 度限制生成树 连通性问题 强大DFS算法 无向连通性 割点 割 二连通分支 有向连通性 强连通分支 2-SAT 最小点基 有向无环 拓扑排序 ...
  • ACM算法模板和pku代码

    2010-11-09 16:15:16
    限制长度最短路,负环判连通,点权变边权,改变正负号 表达式求值 算法优先算法求表达式值 词法分析与算法优先算法,集合运算:差集,并集,交集 矩阵乘法 线段覆盖数量 矩阵构造,nlogn矩阵乘法 2-SAT XOR ...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象的方法设计代码; 2、一个图是一个类的实例; 3、类...
  • 1 字符串处理 5 1.1 KMP . . . . . . . . ....1.2 e-KMP ....1.3 Manacher ....1.4 AC 自动机 ....1.5 后缀数组 ....1.5.1 DA ....1.5.2 DC3 ....1.6 后缀自动机 ....3.3.1 点 . . . . . . . . . . . . . . . . . . . . . . ...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
关键字:

计算图的最大边权最小生成树