>

天梯赛磨炼,继续畅通工程必发88手机版

- 编辑:www.bifa688.com -

天梯赛磨炼,继续畅通工程必发88手机版

【PTA-天梯赛演练】畅通工程之局地最小开支难点,pta-畅通工程

必发88手机版,某所在经过对村镇交通意况的检察,得到现存乡镇间飞快道路的总计数据,并建议“畅通工程”的靶子:使全部地域其余三个市集间都能够兑现急速通行(但不自然有一向的神速道路相连,只要相互直接通过飞速路可达就可以)。现获得城市和商场征程总结表,表中列出了率性两城市和市集间建筑快捷路的支出,以及该道路是或不是早已修通的情事。现请你编写程序,总结出全地域交通供给的最低资本。

7-1 畅通工程之局部最小开销难题(35 分)

某所在经过对村镇交通情形的实验琢磨,得到现存乡镇间快捷道路的计算数据,并提议“畅通工程”的对象:使一切地区其余八个市场间都得以实现长足交通(但不明显有一直的火速道路相连,只要相互间接通过快速路可达就能够)。现得到城市和市集征程总结表,表中列出了任性两城市和商场间修建火速路的开支,以及该道路是或不是已经修通的气象。现请你编写程序,计算出全地区交通供给的最低资本。

省府“畅通工程”的对象是使全县其余多少个山村间都得以兑现公路交通(但不分明有直接的公路相接,只要能直接通过公路可达就能够)。现获得城市和商场道路计算表,表中列出了大肆两城市和市镇间修建道路的花费,以及该道路是或不是早就修通的景色。现请你编写程序,总结出整个省交通必要的最低资本。 

输入格式:

输入的首先行提交村庄数目N (1≤N≤100);随后的N(N−1)/2行对应村庄间道路的血本及建筑状态:每行给出4个正整数,分别是三个村庄的号子(从1编号到N),此两村庄间道路的工本,以及建筑状态 — 1表示已建,0表示未建。

输入格式:

输入的率先行提交村庄数目N (1≤N≤100);随后的N(N−1)/2行对应村庄间道路的财力及建筑状态:每行给出4个正整数,分别是五个村子的号子(从1编号到N),此两村庄间道路的资本,以及建筑状态 — 1表示已建,0意味着未建。

Input测量试验输入包涵若干测试用例。每个测量检验用例的第1行提交村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的工本及建筑状态,每行给4个正整数,分别是多个村子的号子(从1编号到N),此两村庄间道路的资金财产,以及建筑状态:1表示已建,0表示未建。 

输出格式:

输出全县交通需求的最低资本。

出口格式:

输出全市交通须求的最低资本。

当N为0时输入完成。Output每一种测量检验用例的出口占一行,输出全县交通要求的最低资本。Sample Input

输入样例:

4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0

输入样例:

4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

出口样例:

3

#include<bits/stdc  .h>
using namespace std;
int top[105];
int n,tot=0;         //连通分量初始为0 
struct edge            //边 
{
    int x,y,w;         //x、y是边的两个顶点,w是边的权值 
}a[10005];
int find(int r)
{
    if(top[r]!=r)
    top[r]=find(top[r]);
    return top[r];
}
void init(int n)
{
    for(int i=1;i<=n;i  )
        top[i]=i;
}
bool cmp(edge a,edge b) //边从小到大排列 
{
    return a.w<b.w;
}
int kruskal()
{
    sort(a,a tot,cmp);
    int cnt=0,ans=0,i;
    for(i=0;i<tot;i  )
    {
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx!=fy)
        {
               top[fx]=fy;
               ans=ans a[i].w;
               cnt  ;
        } 
        if(cnt==n-1)break;
    }
    return ans;
}
int main()
{
    int x,y,w,d,i;
    cin>>n;
    init(n);
    for(i=0;i<n*(n-1)/2;i  )
    {
        cin>>x>>y>>w>>d;
        a[tot].x=x;
        a[tot].y=y;
        a[tot  ].w=w;
        if(d!=0)
        {
            int fx=find(x),fy=find(y);
            if(fx!=fy)
            top[fx]=fy;
        }
    }
    printf("%dn",kruskal());
    return 0;
}

某地区经过对村镇交通情况的检察,获得现成乡镇间飞速道路的计算数据,...

输出样例:

3
普里姆算法

#include<iostream>
#include<fstream>
using  namespace std;
#define INF 0x3f3f3f3f
const int maxn = 117;
int m[maxn][maxn];
int vis[maxn], low[maxn];
int n;
int prim()
{
    vis[1] = 1;
    int sum = 0;
    int pos, minn;
    pos = 1;
    for(int i = 1; i <= n; i  )
    {
        low[i] = m[pos][i];
    }
    for(int i = 1; i < n; i  )
    {
        minn = INF;
        for(int j = 1; j <= n; j  )
        {
            if(!vis[j] && minn > low[j])
            {
                minn = low[j];
                pos = j;
            }
        }
        sum  = minn;
        vis[pos] = 1;
        for(int j = 1; j <= n; j  )
        {
            if(!vis[j] && low[j] > m[pos][j])
            {
                low[j] = m[pos][j];
            }
        }
    }
    return sum;
}

int main()
{
    scanf("%d",&n);
    int ms = n*(n-1)/2;
    int x,y,cost,tes;
    for(int i = 1; i <= n ;i   )
        for(int j = 1; j <= n; j  )
        m[i][j] = INF;
    for(int i = 1; i <= ms ; i  )
    {
        cin>>x>>y>>cost>>tes;
        m[x][y] = m[y][x] = tes==1?0:cost;
    }
    cost = prim();
    cout<< cost << endl;
    return 0;
}

  

Sample Output

3
1
0

题解:与之前的有一些变化 需要处理一下 当道路修通时,规定一节点为另一节点的父亲
   用自定义结构体排序再写一遍

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <cstdlib>
 7 #include <iomanip>
 8 #include <cmath>
 9 #include <ctime>
10 #include <map>
11 #include <set>
12 #include <queue>
13 using namespace std;
14 #define lowbit(x) (x&(-x))
15 #define max(x,y) (x>y?x:y)
16 #define min(x,y) (x<y?x:y)
17 #define MAX 100000000000000000
18 #define MOD 1000000007
19 #define pi acos(-1.0)
20 #define ei exp(1)
21 #define PI 3.141592653589793238462
22 #define INF 0x3f3f3f3f3f
23 #define mem(a) (memset(a,0,sizeof(a)))
24 typedef long long ll;
25 ll gcd(ll a,ll b){
26     return b?gcd(b,a%b):a;
27 }
28 bool cmp(int x,int y)
29 {
30     return x>y;
31 }
32 const int N=10005;
33 const int mod=1e9 7;
34 int f[N];
35 struct edge
36 {
37     int u,v,w,flag;
38     bool operator <(const edge &other)const
39     {
40         return w<other.w;
41     }
42 }a[N];
43 void init()
44 {
45     for(int i=1;i<=N;i  )
46         f[i]=i;
47 }
48 int find1(int x)
49 {
50     if(x!=f[x])
51         f[x]=find1(f[x]);
52     return f[x];
53 }
54 int main()
55 {
56     std::ios::sync_with_stdio(false);
57     int n,m;
58     while(scanf("%d",&n)&&n){
59         init();
60         m=n*(n-1)/2;
61         for(int i=0;i<m;i  ){
62             scanf("%d %d %d %d",&a[i].u,&a[i].v,&a[i].w,&a[i].flag);
63             if(a[i].flag) f[a[i].u]=a[i].v;
64         }
65         sort(a,a m);
66         int s=0;
67         for(int i=0;i<m;i  ){
68             int u=a[i].u,v=a[i].v,w=a[i].w;
69             if(find1(u)==find1(v)) continue;
70             f[find1(u)]=find1(v);
71             s =w;
72         }
73         printf("%dn",s);
74     }
75     return 0;
76 }

本文由必发88手机版发布,转载请注明来源:天梯赛磨炼,继续畅通工程必发88手机版