1. 繁忙的都市
【问题描述】
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市*的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
【输入格式】
第一行有两个整数n,m表示城市有n个交叉路口，m条道路。
接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000，1≤m≤50000)。
【输出格式】
两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。
【样例输入】
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
【样例输出】
3 6
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = ;
int n, m;
int x[maxn], y[maxn], f[maxn];
int ans = ; struct node {
int x, y;
int val;
}dis[]; bool cmp(node a, node b) {
return a.val < b.val;
} int find(int x) {
int r = x;
while(r != f[r]) r = f[r];
int i = x, j;
while(f[i] != r) {
j = f[i];
f[i] = r;
i = j;
}
return r;
} void merge(int x, int y) {
x = find(x);
y = find(y);
if(x != y) f[y] = x;
} int main() {
cin >> n >> m;
for(int i = ; i <= m; i++) {
cin >> dis[i].x >> dis[i].y >> dis[i].val;
}
for(int i = ; i <= n; i++) f[i] = i;
sort(dis + , dis + m + , cmp);
int tmp = , maxn = ;
for(int i = ; i <= m; i++) {
if(find(dis[i].x) != find(dis[i].y)) {
merge(dis[i].x, dis[i].y);
tmp++;
maxn = max(maxn, dis[i].val);
}
if(tmp == n - ) break;
}
cout << tmp << ' ' << maxn;
return ;
} /*
5 5
1 2 3
1 4 5
2 5 7
2 3 6
3 5 10 2 1
1 2 100 100 5
1 10 3
10 32 5
21 50 7
40 80 6
50 99 10 */
2．最优布线问题
【问题描述】
学校有n台计算机，为了方便数据传输，现在要将它们用数据线连接起来。两台计算机被连接是指它们有数据连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
【输入格式】
第一行为整数n（2≤n≤100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
【输出格式】
一个整数，表示最小的连接费用。
【样例输入】
3
0 1 2
1 0 1
2 1 0
【样例输出】
2
#include<iostream>
#include<cstring>
using namespace std;
int g[][];
int minn[];
bool u[];
int n,i,j;
int main()
{
cin >> n;
for(i = ; i <= n; i++){
for(j = ; j <= n; j++){
cin >> g[i][j];
}
}
memset(minn,0x7f,sizeof(minn));
minn[] = ;
memset(u,,sizeof(u));
for(i = ; i <= n; i++){
int k = ;
for(j = ; j <= n; j++){
if(u[j] && minn[j] < minn[k]){
k = j;
}
}
u[k] = false;
for(j = ; j <= n; j++){
if(u[j] && g[k][j] < minn[j]){
minn[j] = g[k][j];
}
}
}
int total = ;
for(i = ; i <= n; i++){
total += minn[i];
}
cout << total << endl;
return ;
}
/*
3
0 1 2
1 0 1
2 1 0 2
0 1 2
1 0 1 4
0 1 2 1
1 0 3 2
2 1 1 3
3 0 3 1 5
0 1 2 1 3
1 0 3 2 1
2 1 1 3 2
3 0 3 1 2
4 1 2 1 3
*/
1．矩阵游戏
【问题描述】
小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：
行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）；
列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）；
游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小Q决定写一个程序来判断这些关卡是否有解。
【输入格式】
第一行包含一个整数T，表示数据的组数。
接下来包含T组数据，每组数据第一行为一个整数N（N ≤ 200），表示方阵的大小；接下来N行为一个N*N的01矩阵（0表示白色，1表示黑色）。
【输出格式】
包含T行。对于每一组数据，如果该关卡有解，输出一行Yes；否则输出一行No。
【样例输入】
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
【样例输出】
No
Yes
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,lnk[][],p[];
bool vis[];
int read() {
int ret=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') ret=ret*+ch-'',ch=getchar();
return ret;
}
bool DFS(int x) {
for(int j=; j<=lnk[x][]; j++)if(!vis[lnk[x][j]]) {
vis[lnk[x][j]]=;
if(!p[lnk[x][j]]||DFS(p[lnk[x][j]])) {
p[lnk[x][j]]=x;
return ;
}
}
return ;
}
int main() {
T=read();
bool flg;
while(T--) {
n=read();
for(int i=; i<=n; i++) {
p[i]=lnk[i][]=;
for(int j=; j<=n; j++) if(read()) lnk[i][++lnk[i][]]=j;
}
flg=;
for(int i=; i<=n; i++) {
memset(vis,,sizeof vis);
if(!DFS(i)) {
puts("No"),flg=;
break;
}
}
if(flg) puts("Yes");
}
return ;
}
/*
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0 1
3
1 1 0
0 1 0
1 0 0 3
1
1
1
0
2
1 1
1 0 3
2
0 0
0 0
2
1 1
1 1
4
1 0 1 0
0 1 0 1
1 0 0 0
1 1 1 1 */