九度-1024

# 题目描述： #

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

# 输入： #

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

# 输出： #

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

# 样例输入： #

# 样例输出： #

3
?

# 代码 #

#include<cstdio>  
#include<cstring>  
#include<cmath>  
#include<algorithm>  
#define INF 100000001  
using namespace std;  
int a[1001];  
struct lx  
{  
int x,y,c;  
}l[5001];  
int intset(int n)  
{  
for(int i=0; i<=n; i++)  
    a[i]=i;  
}  
int fa(int x)  
{  
if(x!=a[x])  
    x=fa(a[x]);  
return a[x];  
}  
bool cmpa(lx t1,lx t2)  
{  
return t1.c<t2.c;  
}  
int main()  
{  
int n,m;  
while(scanf("%d%d",&n,&m),n)  
{  
    for(int i=0;i<n;i++)  
    scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].c);  
    int x,y;  
    intset(m);  
    sort(l,l+n,cmpa);  
    int ans=0;  
    for(int i=0;i<n;i++)  
    {  
        x=fa(l[i].x);  
        y=fa(l[i].y);  
        if(x!=y)  
        {  
            ans+=l[i].c;  
            a[y]=x;  
        }  
    }  
    int s=0;  
    for(int i=1;i<=m;i++)  
    if(a[i]==i)s++;  
    if(s>1)puts("?");  
    else  
    printf("%d\n",ans);  
}  
}

# 作者提醒 #

还是最小生成树。

就是加一个状态检查，能否连接所有的点。

九度-1026

# 题目描述： #

输入两个不超过整型定义的非负10进制整数A和B(<=231-1)，输出A+B的m (1 < m <10)进制数。

# 输入： #

输入格式：测试输入包含若干测试用例。每个测试用例占一行，给出m和A，B的值。
当m为0时输入结束。

# 输出： #

输出格式：每个测试用例的输出占一行，输出A+B的m进制数。

# 样例输入： #

8 1300 48
2 1 7
0

# 样例输出： #

2504
1000

# 代码： #

#include <iostream>  
#include <stack>  
using namespace std;  

int main(){  
int m;  //表示m进制数字  
unsigned int A,B;  
stack<int>s;  
while(cin>>m){  
    if(m == 0)  
        break;  
    while(!s.empty())  
        s.pop();  
    cin>>A>>B;  
    long long temp = A + B;  
    while(temp >= m){  
        long long result = temp % m;  
        temp = temp / m;  
        s.push(result);  
    }  
    s.push(temp);  
    while(!s.empty()){  
        cout<<s.top();  
        s.pop();  
    }  
    cout<<endl;  
}  
return 0;  
}

# 作者提醒 #

这道题目的关键是数据的表示问题，
因为A，B的大小问题，如果设置成int型会通不过，因为在运算A+B的时候，会溢出。
所以定义A,B时，用unsigned或者 long long。 本题中，根据进制与数字的关系，
用栈最能体现这种关系。当然用数组来保存每位数字，或者直接在每次得到余数之后输出也是可以的。
最后注意格式，要在输出数字之后换行。